A Milanban nevelkedett, bár soha nem játszott a piros-feketék csapatában. Kölcsönben játszott a Verona (1990–91) Trento (1991–92) és a Ravenna (1992–93) gárdájában is. Ezután a Fiorentina csapatát erősítette nyolc éven keresztül. Kétszer volt a violákkal kupagyőztes, és bemutatkozott a Bajnokok Ligájában is. 2000-ben az év kapusának választották a Seria A-ban. Több mint 200 bajnokit játszott a Fiorentina színeiben, a klub csődbemenetele előtt egy évvel, 2001-ben az Internazionalehoz igazolt, ahol első számú hálóőrnek számított egészen 2005 nyaráig a brazilJúlio César érkezéséig. Miután már nem ő számított az első számú kapusnak több csapattal is hírbe hozták, de meghosszabbította a szerződését és a megegyezés értelmében Toldo 2010-ig, azaz visszavonulásáig az Inter játékosa maradt. A milánói kék-fekete csapattal megnyert minden fontos hazai címet, az Inter szinte egyeduralkodó volt a 2006-os bundabotrány, a Calciopoli, és a Juventus kizárása után. Zsinórban ötször nyerték meg a bajnokságot, majd a 2009–2010-es szezonban az európai porondon is csúcsra értek, miután 2–0-ra legyőzték a FC Bayern Münchent a Bajnokok Ligája döntőében.
Toldo pályafutása során 2004 végéig 28-szor szerepelt a válogatottban. 1995 október 8-án mutatkozott be a Scuadra Azzurrában a horvátok elleni 1–1 alkalmával. 2000-es labdarúgó Európa-bajnokság előtt nyolc nappal Gianluigi Buffon eltörte a karját a Norvégia elleni barátságos mérkőzésen és Toldo-t választották a válogatott kapusának. Az elődöntőben a hollandok ellen bravúrt bravúrra halmozott, miután a rendes játékidőben és a tizenegyes párbaj során is 2–2 tizenegyest hárított. A döntőben viszont nem tudta hárítani Sylvain Wiltord lövését, amivel a franciák kihúzták hosszabbításra és végül David Trezeguet aranygóljával megnyerték az Európa-bajnokságot.
