A simple formulation is proposed to establish some explicit criteria for testing the Hurwitz stability of a complex interval matrix. In contrast to the existing methods, which are nearly all developed to special types of complex interval matrices, our method is applicable to complex interval matrices without any restrictions. In addition, by use of the proposed formulation it becomes fairly clear that the problem of the Hurwitz stability of complex interval polynomials can be treated as a special case of that of complex interval matrices. For complex interval polynomials, some new stability criteria, which are completely different from those based on the Kharitonov theorem, are also derived explicitly. Our formulation is helpful to analyze the stability of a complicated system involving parametric uncertainties. The criteria presented in this paper are all formulated in terms of the structured singular value, which is a widely used index in analyzing uncertain control systems and can be evaluated by existing softwares. Several examples are given to illustrate the proposed results.