In order to improve the registration efficiency of three-dimensional point cloud, a two-step point cloud registration algorithm is proposed based on the key point initial matching using the normal vector distribution feature and the accurate registration using the iterative closest point (ICP). Firstly, the definition of the adjacency region and the normal vector distribution feature model of point cloud are presented, and a key point selection algorithm is proposed based on the model. Secondly, the fast point feature histograms of key points are calculated using the local coordinate system, and the false matches are eliminated by the sampling conformance registration algorithm. According to the corresponding relation, the rotation and translation matrices are calculated and the initial registration is completed. Finally, the final registration result is obtained using ICP algorithm. The experimental results show that the proposed algorithm can effectively improve the registration efficiency while ensuring the accuracy of the registration in the data of unordered point cloud and the self-acquired depth point cloud.