Ottimo passista scalatore, Savoldelli passa professionista nel 1986 con la Roslotto-Mg Mobili. Subito si dimostra particolarmente portato per le corse a tappe e nella stagione successiva si classifica 13° al Giro d'Italia. Nel '98 passa alla Saeco e fa ancora meglio vincendo il Giro del Trentino e ottenendo il 9° posto al Giro d'Italia. Nel '99, sempre con i colori Saeco, bissa il successo al Trentino e si presenta al Giro d'Italia come uno dei maggiori antagonisti di Pantani. Vince la 14° tappa (Bra-Borgo San Dalmazzo) precedendo di quasi 2' Pantani (nuova maglia rosa). Successivamente è secondo nella cronometro di Treviso e, dopo l'esclusione di Pantani a Madonna di Campiglio, spetta a lui partire con il simbolo del primato nel tappone che attraverso la Cima Coppi a Passo Gavia porta all'Aprica. Paolo rifiuta però la maglia rosa in segno di solidarietà con il campione romagnolo e sulle rampe del Mortirolo perde il Giro d'Italia a favore di Ivan Gotti. Riesce a difendere il secondo posto precedendo a Milano di un solo secondo Gilberto Simoni, ma è consapevole di aver perso una grande occasione.
Nel 2000 si presenta al Giro d'Italia come favorito, avendo vinto il Giro di Romandia e una tappa del Giro del Trentino, ma cade e finisce il Giro al 24° posto; partecipa anche al Tour (41°) ma ha problemi fisici e solo nel 2001 riesce a rimettersi in sesto grazie ad un osteopata di Parma. Al Giro 2001 esce raramente dall'anonimato, è comunque secondo nella penultima tappa con arrivo ad Arona, e conclude 14° a quasi venti minuti da Gilberto Simoni.
Nel 2002, dopo quattro anni alla Saeco, cambia ambiente e si trasferisce all'Alexia Alluminio, squadra di secondo piano della quale è capitano unico. Al Giro d'Italia gli portarono via (per ragioni di doping) sia Garzelli che Simoni, e lui riesce ad approfittare di questa opportunità strappando la maglia rosa all'australiano Cadel Evans. Non era certo dato tra i grandi favoriti, non ha avuto l'aiuto della squadra, ma ha superato tutti con forza e acume tattico ottenendo finalmente quel successo che gli era sfuggito tre anni prima.
Dopo la corsa rosa lo cerca Lance Armstrong, ma i fatti dell'11 settembre fanno saltare tutto ma Paolo riesce comunque a firmare un vantaggioso contratto di due anni con la Deutsche Telekom, orfana di Ullrich, diventanto l'uomo di punta per il Tour.
Nel mese di febbraio 2003 a Tenerife, durante il ritiro collegiale con la Deutsche Telekom, scendendo in bicicletta dal Teide, il corridore bergamasco si schianta contro una motocicletta che sale dalla direzione opposta, restando per terra tramortito. Quando si riprende, si ritrova all'ospedale con cinque fratture: setto nasale, mandibola superiore, dito della mano e due vertebre spinose. All'ospedale di Bergamo, dove è stato trasportato appena le condizioni lo hanno consentito, il dottor Losapio gli rimette insieme le ossa, gli mette un collare rigido e un cerottone grande a coprire il naso. Arrivata l'estate, mentre sta riprendendo confidenza con la bicicletta, Savoldelli avverte una persistente stanchezza. All'inizio da la colpa alla lunga inattività e alle botte. Passerà pensa. Invece non passa, anzi s'accentua. In un ospedale tedesco, dove i dirigenti della Deutsche Telekom lo fanno ricoverare, gli trovano un virus che gli ha sballato tutti i valori del sangue: bisogna fermarsi di nuovo e ripartire da zero; in pratica arriva la fine della stagione senza praticamente una corsa.
Nel 2004 riparte con cautela e a maggio si schiera al via del Giro di Germania, probante collaudo in vista della partecipazione al Tour a fianco di Ullrich, nel frattempo tornato all'ovile. Ma la sfortuna è di nuovo in agguato: altra caduta, altre cicatrici. Questa volta ad andarci di mezzo sono il radio fratturato, la fronte, le labbra e le guance ferite e contuse. Lo stop, per fortuna, è più breve dell'anno precedente. Paolo rimonta in sella verso la fine dell'estate, disputa un discreto Trittico Lombardo e pedala con i primi a Zurigo, in Coppa del Mondo. Vorrebbe andare alla Vuelta, ma la Telekom non lo convoca nemmeno, fiutando che sta per cambiare squadra. Sospetto più che fondato: Savoldelli, che ha deciso di voltare pagina, firma un biennale con la Discovery Channel, la compagine americana di Lance Armstrong, illudendosi che il cambiamento d'aria sarà anche un talismano contro la sfortuna che lo perseguita.
Ma il 2005 è appena iniziato, siamo a gennaio, e la malasorte colpisce di nuovo. Mentre si sta allenando con Armstrong in California, gli scoppia la camera d'aria della ruota anteriore e si ritrova per l'ennesima volta in terra: questa volta si frattura la clavicola che gli viene saldata con nove viti e una placca. Ma Paolo ha una tempra da montanaro bergamasco che non conosce la parola resa. Ha una tal voglia di tornare a correre che getta il cuore aldilà di ogni ostacolo, compreso quello dei medici, che sono stati categorici: un mese senza toccare la bici. Lui, con un pizzico di sana incoscienza, dimezza i tempi: dopo quindici giorni è già sui rulli, dopo tre settimane sulla strada. Ad aprile affronta le prime corse, poi si testa sulle rampe amiche della Presolana, infine in Romandia si sottopone all'ultimo collaudo.
Al Giro arriva convinto di non poter competere con Basso, Cunego e Simoni. Però sta bene e spera di finire nella loro scia, togliendosi qualche soddisfazione strada facendo. Si presenta in punta di piedi, non fa proclami ma una volta in corsa cambia lo scenario. Il prologo è incoraggiante, le salite appenniniche della prima settimana lo vedono in prima linea, lo frena soltanto un imbottigliamento, causa caduta, sulla salita che porta a Frosinone, dove perde una quarantina di secondi. Da lì in avanti è un crescendo: un'ottima cronometro a Firenze, la vittoria di tappa a Zoldo Alto, la maglia rosa a Ortisei, fino alle grandi emozioni dell'ultima settimana e, soprattutto, dell'epica tappa del Sestrière. Fra Ortisei e Milano sceglie saggiamente di vivere alla giornata, mettendo in evidenza, oltre che la bontà della condizione, una saggezza tattica da campione consumato.
Sceglie con lucida freddezza i punti in cui sarà costretto a limitare i danni, vale a dire le salite più dure dove dovrà concedere qualcosa agli scalatori puri, e quelli in cui, al contrario, dovrà dare tutto per avvantaggiarsi (discese, cronometro). Sulla strada il piano tattico trova perfetta esecuzione.
Savoldelli cede qualche secondo a Rujano e Simoni sul Trepalle, sul Colle di Tenda, sul Colle delle Finestre, ma intanto salva le gambe, che poi gli servono per far tornare i conti nella crono di Torino. È anche furbo, ma questo si sapeva: nei momenti di difficoltà trova alleanze per strada che lo aiutano a salvare la pelle. Anche qui, nulla di nuovo: questa è da sempre una prerogativa dei campioni e il 29 maggio 2005 a Milano Paolo sale per la seconda volta sul gradino più alto del podio del Giro d'Italia, prendendosi una grande rivincita sulla sfortuna e ottenendo un successo costruito con dedizione, sacrificio e regolarità.
Nello stesso anno partecipa anche al Tour de France in qualità di gregario di Lance Armstrong. Si toglie comunque la soddisfazione di contribuire alla vittoria nella cronomentro a squadre e soprattutto di vincere la 17° tappa. Nel 2006 è di nuovo al via con i gradi di capitano al Giro d'Italia. Si dimostra ancora una volta uno dei più forti ciclisti italiani per le corse a tappe, ma non ha la stessa condizione del 2005 e dopo aver vinto la prima cronometro e indossando la maglia rosa, si deve accontentare del quinto posto nella classifica finale.
Nell'agosto del 2006 Savoldelli è ingaggiato, per la stagione 2007, dall'Astana team, squadra del Kazakistan, di cui sarà il capitano al prossimo Giro d'Italia.