This paper presents a new out-of-step detection method for multi-machine power systems based on approximate stability boundaries. The boundaries are constructed based on Zubov's method of stability analysis. The proposed out-of-step detection method first constructs a series of boundaries in power angle - frequency (δ-ω) plane, and tracks the trajectory of each generator in the δ-ω plane after the disturbance to differentiate out-of-step from stable power swings. The electrical parameters needed to construct approximate stability boundaries are obtained directly from Phasor Measurement Units (PMUs) located at the generator's terminal. The effectiveness of the proposed method is tested in a Single Machine Infinite Bus (SMIB) and the IEEE 3-machine 9-bus system. Simulation results show that the proposed algorithm is capable of detecting out-of-step conditions in multi-machine power systems without using network reduction techniques.