Earthquake Early Warning (EEW) algorithms estimate the magnitude of an underway rupture from the first few seconds of the P-wave to allow hazard assessment and mitigation before the S-wave arrival. Many large subduction-zone earthquakes initiate 50–150 km offshore, potentially allowing seafloor instruments sufficient time to identify large ruptures before the S-waves reach land. We tested an EEW algorithm using accelerograms recorded offshore Hokkaido in the region of the 2003 M_w 8.1 Tokachi-Oki earthquake and its aftershocks. A wavelet transform of the first ∼4 s of the P-wave concentrates information about earthquake magnitude from both waveform amplitude and frequency content. We find that wavelets with support of a few seconds provide discriminants for EEW that are both accurate enough to be useful and superior to peak acceleration or peak velocity. Additionally, we observe a scaling of wavelet coefficient magnitude above M_w 6.0 indicating that, at least for the mainshock (M_w 8.1) and largest aftershock (M_w 7.1), the final size of a rupture could have been estimated from the initial portion of the seismogram.