Abstract: A fast scheme based on multi-level substructure technique is proposed to analyze band structure and transmission characteristics of phononic crystals. The main idea is that the finite element model of phononic crystal is divided into several substructures by a special multi-level decomposition. For the calculation of band structure, tree travelling technique and static condensation method are used to convert the internal stiffness matrix into the Bloch boundary of unit cell. Because the internal stiffness matrix does not change along with reduced wave vector, the scheme can reduce computation budget and improve efficiency greatly, while it does not introduce approximation into traditional finite element model. For the calculation of transmission characteristics, the proposed scheme can be also used to reduce computation, because unit cell of phononic crystal is periodic which has the same coefficient matrix. Moreover, the back substitution of internal displacements of unit cell can be selected flexibly. Some examples of three-dimensional locally resonant system and two-dimensional Bragg scattering phononic crystal are analyzed. Numerical results indicate that the proposed scheme is efficient and accurate, and suitable for complex phononic crystal problems.