This paper studies consensus problems of multi-agent systems with binary-valued communications. Different from most existing works, the agents considered in this paper can only get binary-valued observations of its neighbors' states with random noises. A consensus algorithm is proposed: first, each agent estimates its neighbors' states by the recursive projection algorithm; then, each agent designs the control timely based on the estimates. It is proved that the estimates of the states can converge to the true states with a faster convergence rate than that in the parameter estimation. Moreover, the states of the agents can achieve mean-square consensus, and the corresponding consensus speed can achieve O(1/t) under certain conditions. Finally, simulations are given to demonstrate the theoretical results.