Binary code learning, a.k.a. hashing, has received increasing attention in large-scale visual search. By transforming high-dimensional features to binary codes, the original Euclidean distance is approximated via Hamming distance. More recently, it is advocated that it is the manifold distance, rather than the Euclidean distance, that should be preserved in the Hamming space. However, it retains as an open problem to directly preserve the manifold structure by hashing. In particular, it needs first to build the local linear embedding in the original feature space, and then quantize such embedding to binary codes. Such a twostep coding is problematic and less optimized. Besides, the offline learning is extremely time and memory consuming, which needs to calculate the similarity matrix of the original data. In this paper, we propose a novel hashing algorithm, termed Discrete Locality Linear Embedding Hashing (DLLH), which well addresses the above challenges. DLLH directly reconstructs the manifold structure in the Hamming space, which learns optimal hash codes to maintain the local linear relationship of data points. To learn Discrete Locally Linear Embedding (DLLE) codes, we further propose a discrete optimization algorithm with an iterative parameters updating scheme. Moreover, an anchor-based acceleration scheme, termed Anchor-DLLH (ADLLH), is further introduced, which approximates the large similarity matrix by the product of two low rank matrices. Experimental results on three widely used benchmark datasets, i.e. CIFAR10, NUS-WIDE, and Youtube Face, have shown superior performance of the proposed DLLH over the state-of-the-art approaches.