Aiming at the characteristics of stone point cloud with many noise points, high density and complex surface structure, as well as the long registration time and poor robustness of traditional iterative nearest point algorithm, a stone point cloud registration method based on key point selection and sampling consistency was proposed. Firstly, the stone point cloud data were preprocessed by denoising and downsampling. Secondly, the key points were selected by the Angle of the normal vector neighborhood of the point cloud, and the fast point feature histogram was constructed for initial registration. Finally, the corresponding point pairs are found according to the K-dimensional tree structure and the minimum distance from point to surface, and the wrong corresponding point pairs are eliminated by the random sampling consistency algorithm to complete the final registration of point cloud data. Compared with the SAC-IA+NDT algorithm, the results show that the proposed method is 21.12% faster than the SAC-IA+NDT algorithm, and 47.1% more accurate than the GICP algorithm. It can realize the rapid and accurate registration of stone point clouds, and provides a new scheme for the registration of stone point clouds.