To establish a high-precision fault diagnosis model of bolted connection structure in complex working environment, a fault diagnosis model based on the fuzzy soft set and K-Means is proposed for bolted connection structure. The fuzzy soft set theory is introduced to fuzzify the data set, which reduces the uncertain factors that influence the data on the diagnostic model. The ISN parameter reduction algorithm is utilized to remove redundant parameters in the data, which improves the operating efficiency of model. A clustering angle index is combined the clustering degree and the intra-class average angle to calculate the optimal initial clustering center and clustering number of K-Means, which prevents obtaining local optimal results and enhances the fault diagnosis accuracy of the model. Experimental results show that the proposed approach outperforms the K-Means in clustering performance index, fault diagnosis accuracy, and noise resistance.