The locomotive running gear 3D point cloud data are obtained by line-structured laser scanner, and the bolts on the locomotive running gear under the 3D point cloud data are recognized and located automatically. Firstly, fast point feature histograms (FPFHs) of the key points are calculated to describe the 3D features, and the target region is matched with the preselected bolt template. Then, K-means clustering is carried out on the weighted match point set using uniform seed points. Finally, the Hough transform method is used to establish a strict classifier for the clusters, and the existence and precise position of the bolts are determined. The experimental results verify the effectiveness of the proposed method.