15. marca 2004 so oboževalci Georgea Michaela od britanskega pevca po osmih letih končno le dobili nov originalni material, ki ga je zbral pod naslovom Patience. Album Older je namreč luč sveta ugledal leta 1996, čez tri leta pa je sicer izdal četrti album Songs from the Last Century, a je bil ta sestavljen iz samih glasbenih priredb – njegov edini tovrstni album.

Patience je tako njegov peti studijski album, obenem pa je postal tudi zadnji album z izvirnimi pesmimi glasbenika – nekatere vseeno vsebujejo izvlečke iz drugih pesmi –, ki je umrl 25. decembra 2016.

Že pred izidom je sicer napovedal, da bo to zadnji album, ki ga bo prodajal tudi v fizični obliki. "V preteklih letih sem bil izdatno nagrajen za svoje talente, zato res ne potrebujem denarja javnosti. Rad bi imel dobrodelno spletno stran, na kateri lahko vsak brezplačno prenese mojo glasbo, obenem pa, če želi, daruje mojim najljubšim dobrodelnim ustanovam," je takrat dejal v intervjuju za BBC. Ta odločitev naj bi zmanjšala pritisk nanj, da izdaja nove albume, in mu omogočila več zasebnega življenja.

Michael je po več kot desetih letih pesmi izdal pri založbi Sony – leta 1990 jo je namreč zapustil po pravni bitki, v kateri je trdil, da ga pogodba duši in drži v "poklicnem suženjstvu".

Leta 2004 je v intervjuju za britansko revijo Attitude delil, da je bil nad novim projektom, ki ga je snemal vrsto let in v katerem obravnava tudi spolnost in vojno, popolnoma navdušen, ta ga je napolnil z energijo. "V vokalih je veliko bolj samozavestnega, bolj prepričanega," je povedal in dodal, da so na njem razglasitve ljubezni, ki jih – vsaj od delovanja v dvojcu Wham! – ni posnel.

Obenem naj bi še "poglobil resnico" oziroma se tej vsaj želel približati. Za primer je dal z bolečimi spomini polno My Mother Had a Brother in Through, s katero je napadel tabloide. Po mnenju Washington Posta je dokazal eno izmed resnic popa – "da lahko težje ideje dlje potujejo, če letijo na krilih vedrih melodij".

Pesem Patience, ki si deli ime z albumom, je ustvaril na klavirju Johna Lennona – tistega, ki ga je uporabil za legendarno skladbo Imagine. Michael je tega namreč kupil za skoraj dva milijona evrov, saj je hotel zagotoviti, da si ga lahko ogledajo oboževalci Beatlesov.

Prva dva singla, Freeek! in Shoot the Dog, sta bila izdana že leta 2002, ko naj bi album prvotno izšel. Dve leti pozneje so sledili še singli Amazing, Flawless (Go to the City) in Round Here. Vsi so se uvrstili na različne glasbene lestvice po celotnem svetu.

Album Patience je sicer debitiral na prvem mestu britanske lestvice albumov in postal eden najhitreje prodajanih albumov v Združenem kraljestvu. Album je šel v prodajo tudi v ZDA, a ni vseboval pesmi Patience Pt. 2 in Shoot the Dog. Ta naj bi bila sporna zaradi napadov 11. septembra 2001.

Shoot the Dog je protivojna skladba, a se je že ob izidu julija 2002 izkazala za kontroverzno – Michael je bil namreč zelo kritičen do Georgea W. Busha in Tonyja Blaira pred invazijo na Irak leta 2003. "Ljudje gledajo na pesem v kontekstu napada na Ameriko, namesto na Tonyja Blaira," je rekel v intervjuju za MTV in dodal, da je bila pesem namenjena predvsem poudarjanju tega, kar je sam videl kot pomanjkanje resne razprave Blaira o odločitvi o napadu na Irak. "Ne vemo, česa je sposoben Sadam Husein, britanska javnost nima pojma," je še poudaril.

Del videospota je tudi risana različica glasbenika na jedrskem izstrelku na Bližnjem vzhodu in Tonyja ter Cherie Blair v postelji s predsednikom Bushem. Ta podoba naj bi bila mišljena kot poklon videu iz leta 1986 za Land of Confusion skupine Genesis. Risanko so producirali ustvarjalci britanske satirične animirane televizijske oddaje 2DTV.