This paper presents a robust and adaptive out-of-step (OOS) protection algorithm, using wide-area information, that can be applied on tie-lines in observable power systems. The developed algorithm is based upon real-time computation of the system impedance and makes use of the well-known power-angle characteristic. In this way, a setting-less OOS concept in real-time environment is developed, which is applicable for tie-lines in an arbitrary power system. Furthermore, the developed protection algorithm is installed on hardware and is verified by numerous tests. The performance of the new hardware implementation is compared to the traditional impedance-based OOS protection methods. The results confirm that the proposed algorithm detects OOS conditions faster and more reliably than the traditional impedance-based solutions.