Binary descriptors not only are beneficial for similarity search, they are also capable of serving as discriminant features for classification purpose. In this paper we propose a new algorithm based on cross entropy to learn effective binary descriptors, dubbed CE-Bits, providing an alternative to L-2 and hinge loss learning. Because of the usage of cross entropy, a min-max binary NP-hard problem is raised to optimize the binary code during training. We provide a novel solution by breaking the binary code into independent blocks and optimize them individually. Although sub-optimal, our method converges very fast and outperforms its L-2 and hinge loss counterparts. By conducting extensive experiments on several benchmark datasets, we show that CE-Bits efficiently generates effective binary descriptors for both classification and retrieval tasks and outper-forms state-of-the-art supervised hashing algorithms.