In this study, we integrate the contour integral-based eigenvalue solution algorithm with a multi-level substructuring method to develop an efficient approach for solving structural vibration analysis and phononic crystal band structure analysis problems. The proposed method first embeds the condensation and back-substitution process of the multi-level substructuring technique into the contour integral algorithm, thereby enabling its application to substructural models. Furthermore, by employing the Guyan condensation procedure inherent in the substructuring method, the eigenvalue distribution for the structural vibration analysis problem is predicted in advance, eliminating the prerequisite of knowing the eigenvalue distribution before executing the contour integral computation. In addition, the algorithm is extended to address phononic crystal band structure analysis; by optimizing the contour integral-based band structure analysis process for master–slave degrees of freedom, the computation of the band structure is markedly accelerated. Finally, three numerical examples validate the high efficiency of the proposed algorithm in solving both structural vibration problems and phononic crystal band structure analysis problems. Based on these numerical examples, the proposed method reduces the number of iterations by employing the contour integral technique and avoids multiple matrix decompositions in band structure analysis by using the condensation technique of the multi-level substructuring method, thereby improving the computational efficiency by more than threefold without compromising accuracy. Furthermore, for larger-scale problems, the proposed method demonstrates even greater computational efficiency.