Abstract: The highly efficient binary representation scheme has dominated the world of computation for a long time. However, the deterministic binary representation seems to be challenged in stochastic neural computation which makes use of the random noise to escape from local minima. This paper presents a novel stochastic binary neural network which uses stochastic weights and the 'Stochastic binary sequence' data representation. It is very attractive with its great potential to be implemented efficiently. Both the feedforward and the recurrent stochastic binary networks have been discussed in depth. The gradient descent learning techniques are described for the feedforward network. A novel simulated annealing method and an incremental Boltzmann learning algorithm have been proposed. Simulation results on the PARITY problem and a face recognition task show the excellent performance of the model.