Constructing a good graph to represent data structures is critical for many important machine learning tasks such as clustering and classification. Recently, a nonparameteric graph construction method called L1-graph is proposed with claimed advantages on sparsity, robustness to data noise and datum-adaptive neighborhood. However, it suffers a lot from the loss of locality and the instability of perfor- mance. In this paper, we propose a Locality-Preserving L1-graph (LOP-L1), which preserves higher local-connections and at the same time maintains sparsity. Besides, compared with L1-graph and the succeeding regularization-based tech- niques, our LOP-L1 requires less amount of running time in the scalability test. We evaluate the effectiveness of LOP-L1 by applying it to clustering application, which confirms that the proposed algorithm outperforms related methods.