The key function of rotating machine condition monitoring (CM) is to detect structural changes during machine operations. This paper presents a novel statistical time-frequency analysis method for this purpose. In particular, frequency spectrum is extracted from the machine condition signals based on periodogram estimation. Undirected weighted graph is then constructed from the resulting periodograms, where the so-called median graph is introduced and adopted to describe the normal machine status. Statistical analysis is performed to investigate newly observed data with respect to the median graph for change decision making. The proposed method has been applied to three different engineering applications to evaluate its effectiveness: load CM; early bearing failure detection; and speed CM. The results were compared with some benchmark methods reported in the literature, where significant improvements of the proposed method were demonstrated, indicating its good potentials in engineering applications.