Real time monitoring of wave height in the ocean far from the coast can contribute to mitigation of a tsunami disaster. Here we demonstrate that early detection of a damaging tsunami can be achieved using a new long baseline kinematic GPS method, by tracking the anomalous changes in sea surface heights. The movement of a GPS buoy relative to a base station with a baseline length of 500 km has been monitored in quasi-real time mode, and the tsunami waves caused by the 5 September 2004 Off Kii Peninsula earthquake, Japan, have been successfully resolved. Based on the continuous analysis of GPS buoy data for 8 days, the average scattering of the low-pass filtered 1-Hz GPS buoy heights after tidal correction are about 3.4 cm and 1.2 cm for typhoon and calm weather, respectively. That is precise enough to detect tsunami waves with an amplitude of over 30 cm even under typhoon conditions. The long baseline can ensure an adequate evacuation time for people living on the coast.