A pair-wise point cloud registration method based on normal distribution similarity was proposed to solve the problem of slow efficiency and low accuracy of existing “point-to-point” pair-wise point cloud registration algorithms. The traditional “point-to-point” registration problem was transformed to a “distribution-to-distribution” registration problem. The K-means clustering algorithm was used to generate several clusters as normal distributions to fit the original point cloud data, and then these normal distributions were used for registration, in order to reduce the calculation overhead and improve the registration efficiency. Kullback-Leibler divergence was introduced to evaluate the similarity of the nearest neighbor distributions to reduce the negative effect of non-overlapping data regions on registration in order to improve the registration accuracy. The final registration result can be obtained by using Lie algebra solver on the basis of the above steps. Eight other pair-wise point cloud registration methods were selected for comparison, including a lot of traditional “point-to-point” registration methods, in order to verify the effectiveness of the proposed method. The experimental results showed that the proposed algorithm could effectively improve the stability and accuracy of the registration tasks while keeping the computation cost low. In addition, experiments on two datasets in real scenarios further proved that the proposed algorithm had good application potential in real environment registration tasks.