The main goal of an earthquake early warning system (EEWS) is to estimate the magnitude of an underway rupture from the first few seconds in order to allow hazard assessment and mitigation before destructive events occur. This letter investigates the application of a wavelet-based algorithm for local magnitude estimation in the South Aegean Sea (focusing on Crete Island) which is covered by a sparse seismological network. A relation between the first few seconds of the first-arriving energy at the surface, the P wave, and the local magnitude of the earthquake has been developed for the area of interest. Results show that the errors produced by the proposed method present less scattering than relevant magnitude rapid estimation methods. It is the first time that such a method is applied in a sparse seismological network since all the previous studies took place in high-density networks. This fact expands the applicability of EEWS and also provides an alternative magnitude estimator for the currently developed EEWS.