A wealth of complex structures with interconnected joints such as steel truss bridges and warehouses commonly exist in civil engineering, while they are easily subjected to joint faults like bolt loosening, breathing crack and chemical corrosion during their service, which would seriously affect structures’ safety, durability and reliability. Therefore, diagnosis of joint faults, especially at an early stage, would be essential and meaningful for complex structures. To overcome some limitations in existing diagnosis methods, a novel frequency domain feature-based approach for joint faults in complex structures is developed in this paper. In the new approach, complex structures are simplified as some simple and discrete unit substructures. Then, corresponding unit dynamic models are obtained for the dynamic analysis by considering effects of potential faults as additional nonlinear loads. Collecting vibration data of complex structures to be diagnosed only under different levels of harmonic excitations, which have different magnitudes but same frequency components, local frequency domain diagnosis features and indicators based on additional nonlinear loads and transmissibility functions are defined, and detailed procedures of the novel approach are shown accordingly. Finally, effectiveness and availability of the novel approach are verified through some experiments on a steel structure with bolted joints. Moreover, results of comparison study and effects of excitation frequency are discussed to show superiority of the proposed approach further.