Jaunās tūkstošgades sākumā PJ Hārvija bauda sava darba augļus, jo albums „Stories from the City, stories from the Sea” iegūst prestižo Mercury Prize un Hārvija, starp citu ir pirmā sieviešu kārtas māksliniece, kas saņēmusi šo apbalvojumu, ko reizi gadā piešķir britu un īru labākajiem mūziķiem. Šajā diskā māksliniece miksē sev netipiski maigu melodisku poproku ar jau ierasto ģitāras pancisko skanējumu. Ierakstā dalību ņēmis arī grupas Radiohead dziedājs Toms Jorks (Tom Yorke).
2001. gadā respektablais britu mūzikas žurnāls Q aicina savus lasītājus balsot par 100 ietekmīgākajām sievietēm roka dziedātājām un šeit nu ļaudis ieceļ PJ Hārviju pašā saraksta virsotnē. Nākamos pāris gadus viņa strādā pie jauna materiāla, pa laikam piedalās arī kāda laikabiedra vai līdzīgi domājoša mūziķa ierakstos, tostarp vienojas kopdarbā ar grupu Queens of the Stone Age. 2003. gadā uzstājoties festivālos viņa jau izpilda vairākus skaņdarbus no topošā jaunā ierakstu apkopojuma un 2004. gadā beidzot nodod to fanu kārajām ausim albumu „Uh Huh Her”.