Redigerer Paul Simon (avsnitt)

=== 1999–2007: ''You're the One'' og ''Surprise'' ===

After ''The Capeman'', havnet Simons karriere igjen i en uventet krise. Likevel, gikk Simon inn idet nye millenniumet der han fortsatt hadde et respektabelt omdømme og ga ut nytt kritikerrost materiale med kommersielt utbytte. Simon dro ut på en turné i Nord-Amerika med [[Bob Dylan]] i 1999, der begge byttet om å være hovedartisten i showet og noen ganger opptrådte sammen. Turnén varte fra begynnelsen av juni og sluttet  18. september. Samarbeidet mellom Simon og Dylan ble godt tatt imot av kritikerne, bortsett fra Seth Rogovoy fra avisen ''The Berkshire Eagle'', som svar tvilende til samarbeidet.

I et forsøk på tilbakekomst til musikkmarkedet, skrev og spilte Simon raskt inn et nytt album, ''You're the One'', utgitt i oktober 2000. Albumet bestod for det meste av folkrock/folkpop kombinert med fremmed musikk, særlig med elementer fra Nord-Afrika. Og selv om det forrige albumet ikke gjorde det spesielt bra på hitlistene, så klatret ''You're the One'' inn på hitlistene i Storbritannia og på American Top 20. Albumet fikk gode kritikker, og fikk en Grammy nominasjon som "Album of the Year". Simon turnerte mye for å reklamere for albumet, og en opptreden i Paris ble utgitt på video.

Etter [[Terrorangrepet 11. september 2001]] sang Simon «Bridge Over Troubled Water» på konserten "America: A Tribute to Heroes" som et bidrag til "September 11 Telethon Fund" og bidro med "The Boxer" på den første episoden av ''[[Saturday Night Live]]'' etter 11. september.  I 2002, skrev han og spilte inn «Father and Daughter», en sang for [[animasjon]]sfilmen ''The Wild Thornberrys Movie''. Sporet ble nominert til ''[[Oscar for beste sang]]''.

I 2003 kom Simon og Garfunkel sammen igjen da de mottok en [[Grammy Lifetime Achievement Award]] og ledet til en turné i USA, kalt "Old Friends". Etter det, i 2004 ble det en det til en internasjonal turné, og en gratiskonsert ved [[Colosseum]] i [[Roma]] ble besøkt 600.000 tilskuere. I 2005 sang paret «Mrs. Robinson» og «Homeward Bound», pluss «Bridge Over Troubled Water» sammen med Aaron Neville, på konserten "From the Big Apple to The Big Easy – The Concert for New Orleans", også utgitt som DVD, til støtte til ofre for [[Orkanen Katrina]].

I 2004, ble Simons studioalbum utgitt igjen både individuelt og sammen i en begrenset antall ni-CD-er [[Samleboks]], kalt ''Paul Simon: The Studio Recordings 1972–2000''. Samtidig jobbet Simon med et nytt new album sammen med [[Brian Eno]] kalt ''Surprise'', som ble utgitt i mai 2006. Mesteparten av albumet var inspirert av 11. September 11 terrorismen og [[Irak-krigen]]. Personlig var Simon også inspirert at han fylte 60 år i 2001, som han med humor refererte til på låten "Old" fra albumet ''You're the One''. «Surprise» ble en kommersiell hit, og havnet som nummer 14 på ''[[Billboard 200]]'' og ble nummer 4 i Storbritannia. De fleste kritikerne roste albumet, og mange av dem kalte det et "comeback". Stephen Thomas Erlewine fra [[AllMusic]] skrev at "Simon doesn't achieve his comeback by reconnecting with the sound and spirit of his classic work; he has achieved it by being as restless and ambitious as he was at his popular and creative peak, which makes ''Surprise'' all the more remarkable." Albumet ble støttet med den suksessfulle turnéen ''Surprise Tour'' fra mai til november 2006.

I mars 2004, publiserte Walter Yetnikoff en bok kalt ''Howling at the Moon'', der han kritiserte Simon personlig og for hans ''tvilsomme'' forbindelse med Columbia Records. I 2007 mottok Simon "The Gershwin Prize for Popular Song", gitt av [[Library of Congress]].