Toldo begon zijn clubcarrière bij AC Milan, maar speelde nooit een officiële wedstrijd voor deze club. Na een seizoen bij Trento en een seizoen bij Ravenna kwam de keeper in 1993 uit bij Fiorentina. Voor deze club speelde Toldo acht seizoenen in het basiselftal en kwam hij in onder meer de Champions League uit. In 2001 vertrok hij naar Internazionale, waar hij tot 2005 de eerste keeper was, waarna hij zijn plek in het basiselftal verloor aan de Braziliaan Júlio César. Hoewel hij in 2006 nog even zijn plek als eerste keeper heroverde, werd hij toch weer tweede keeper. In november 2006 scoorde hij de enige goal uit zijn carrière toen hij bij een corner mee naar voren ging in de wedstrijd tegen Juventus die daardoor op 1-1 eindigde.
Nationaal elftal
Toldo speelde tussen 1995 en 2004 in totaal 28 keer voor het nationale elftal van Italië. Tijdens Euro 2000 verdedigde hij het Italiaanse doel en stopte hij in de reguliere speeltijd van de wedstrijd tegen Nederland twee penalty’s, in de penaltyreeks na een 0-0 eindstand stopte hij nog eens drie penalty’s, waarna Italië uiteindelijk in de finale door Frankrijk verslagen werd en Frankrijk Europees kampioen werd . Hoewel hij ook als reserve mee ging naar twee andere EK's en twee WK's, speelde hij hierop geen wedstrijden.
Italië
Kroatië – Italië 
Hongarije – Italië 
Moldavië – Italië 
Bosnië en Her. – Italië 
Noorwegen – Italië 
Turkije – Italië .svg){kind=small}
België – Italië 
Nederland – Italië 
Frankrijk – Italië 
Tsjechië – Italië .svg){kind=small}
Polen – Italië 
Fiorentina