The 26 December 2004 Sumatra earthquake (Mw 9.2--9.3) generated the most deadly tsunami in history. Yet within the first hour, the true danger of a major oceanwide tsunami was not indicated by seismic magnitude estimates, which were far too low (Mw 8.0--8.5). This problem relates to the inherent saturation of early seismic-wave methods. Here we show that the earthquake's true size and tsunami potential can be determined using Global Positioning System (GPS) data up to only 15 min after earthquake initiation, by tracking the mean displacement of the Earth's surface associated with the arrival of seismic waves. Within minutes, displacements of >10 mm are detectable as far away as India, consistent with results using weeks of data after the event. These displacements imply Mw 9.0 ¿ 0.1, indicating a high tsunami potential. This suggests existing GPS infrastructure could be developed into an effective component of tsunami warning systems.