Supercomputers based on parallel systems have always been a hot research topic in academia and industry. As the basis of parallel systems, the properties of interconnection network determine the system performance directly. As a variant of hypercube, cross-cube is a significant interconnection network, which has superior properties such as low diameter compared with hypercube. This paper uses PMC diagnostic model and graph theory method to study the exact value of the diagnostic degree of cross-cube in fault situation. Then, a diagnosis algorithm is proposed and its time complexity is analyzed. Furthermore, simulation experiments verify that the diagnostic algorithm has higher efficiency than some literature algorithms under a variety of fault parameters. Our research can measure the reliability of cross-cube more accurately.