A novel second-order output spectrum (SOOS) based method with a local tuning approach (LTA) is proposed in this paper to locate multiple bolt-loosening faults in complex structures. This new method utilizes a more general multi-degree-of-freedom (MDOF) model with nonlinear components, due to not only bolt-loosening faults but also inherently existing nonlinearity in structures, to derive the SOOS of virtual beam-like structures. Through the LTA, one extra equation is given to derive the local SOOS based damage indicator. In numerical study, the results of comparison with previous methods demonstrate that the fault feature in proposed method provides more local characteristics. Hence, this novel SOOS based method gives more accurate information about the fault location and can be used as an effective and reliable nondestructive evaluation method (NDE) for the detection and location of multiple faults in complex structure with inherent nonlinearity.