Metachromatic leukodystrophy (MLD) is a rare inherited disorder of lysosomal storage, caused by a deficiency in the arylsulfatase A (ARSA) enzyme, leading to toxic accumulation of sulfatides, which progressively impair motor and cognitive function. MLD is a candidate for inclusion in newborn screening (NBS) programs, due to the narrow pre-symptomatic window for effective therapeutic intervention. We set up a prospective pilot NBS program for MLD in Tuscany, based on a two-step approach. The first-tier test quantified four sulfatides; if levels exceeded the cut-off, we performed the second-tier test by measuring ARSA activity on the same neonatal dried blood spot (DBS). We performed the first-tier test on 42,262 newborns over two years and the second-tier test on residual neonatal DBS from 90 of them (0.21%). We recalled 10 newborns (0.02%) for an additional DBS, due to insufficient residual material for a second-tier test (n = 4) or to low ARSA activity (n = 6). We found normal ARSA activity in all new DBS and identified no new cases of MLD. Retrospective analysis of eight neonatal and fifteen non-neonatal DBS from patients with genetically confirmed MLD showed that the algorithm accurately identified MLD patients. This diagnostic algorithm proved feasible and accurate for early detection of MLD in prospective NBS.