Den 15 juli 1959 tillkännagavs det att Presley, efter sin frigivning från den amerikanska armén, skulle göra sitt första tv-framträdande i Frank Sinatras fjärde och sista Timex-sponsrade varietéshow. För specialprogrammet, som ursprungligen hette Frank Sinatras Welcome Home Party for Elvis Presley, skulle han få 125 000 dollar, vilket vid den tiden var en oerhörd summa för ett enda tv-framträdande. Sinatra var inte nöjd med Presleys arvode, eftersom han visste att det översteg hans ersättning för att vara värd för hela programmet. Han accepterade, medveten om att Presleys framträdande skulle locka till sig enorma tittarsiffror för timmen, något som hans tre tidigare specialprogram inte hade lyckats med. Presleys manager, överste Tom Parker, klargjorde också att denna summa endast gällde två låtar, cirka 6-8 minuter. Parker hade hoppats att Presley i Sinatras show skulle åter introducera honom för en äldre publik, en mognare målgrupp som var mindre benägen att avfärda honom till förmån för nästa tonårsidol. TV-specialen skulle sammanföra två av musikvärldens största stjärnor, var och en med sina egna legendariska titlar; Sinatra var känd som ”The Voice” och Presley var känd som ”The King”. Parker var medveten om den publicitet som en sådan mediehändelse skulle medföra och var angelägen om att se till att detta tillfälle skulle gå så smidigt som möjligt för hans klient.
Den 3 mars 1960 återvände Presley, 25 år gammal, till USA från Västtyskland. Sinatra hade ordnat så att hans dotter Nancy skulle vara en del av välkomstfesten och överlämna en låda med skjortor till Presley å sin fars vägnar. På frågan om vilka hans nuvarande favoritsångare var nämnde Presley Sinatra tillsammans med Dean Martin, Patti Page och Kitty Kallen. Två dagar senare, två år efter det att han hade blivit inkallad till den amerikanska armén, blev Presley hedervärt avskedad. Två veckor senare var han i Nashville, Tennessee, för att spela in nytt material för en efterlängtad singel och ett album. Två låtar som han spelade in den 21 mars valdes ut som de två sidorna av hans första singel efter armén, och de låtar som han skulle framföra live i TV-specialen; ”Stuck On You” och ”Fame And Fortune”. Samma dag, efter att ha färdigställt ytterligare två låtar till albumet, gick Presley ombord på ett tåg från Nashville till Miami, Florida. När Presley anlände till Miami nästa dag checkade han in på Fontainebleau Hotel, där showen skulle spelas in. Han tillbringade resten av veckan med att repetera inför showen, som skulle spelas in den 26 mars, och träffade Sinatra för att marknadsföra showen i ett noggrant iscensatt möte som fotograferades för pressutgivning.
Mötet mellan de två följdes ivrigt av media. Sinatra och Presley hade varit musikaliska rivaler sedan 1950-talet, och vid enstaka tillfällen hade de båda tillfrågats om sina åsikter om den andre. Sinatra hade 1957 skrivit en artikel i en fransk tidskrift, Western World, där han beskrev rock’n’roll-musiken som ”sjungen, spelad och skriven till största delen av kretinösa gorillor och med hjälp av sina nästan imbecilla upprepningar och listiga, lurviga – i själva verket smutsiga – sångtexter, och som jag sa tidigare, lyckas den bli krigsmusik för varje sidobrännad brottsling på jordens yta … denna här ransigt luktade afrodisiakum som jag avskyr”. När Presley fick frågan om hur han reagerade när han hörde detta svarade han: ”Han har rätt till sin åsikt, men jag kan inte se att han slår på den utan anledning. Jag beundrar honom som artist och skådespelare, men jag tror att han har fel om detta. Om jag minns rätt var han också en del av en trend. Jag förstår inte hur han kan kalla dagens ungdomar för omoraliska och kriminella.” Pressen, antingen känd eller okänd för Sinatra och Presley, försökte orsaka en spricka mellan paret. De hade dock inget annat än goda saker att säga om varandra när de specifikt tillfrågades om hur de kände. Sinatra svarade på en specifik fråga om Presleys sångstil: ”Det får tiden utvisa. De sa att jag var ett missfoster när jag först slog igenom, men jag finns fortfarande kvar. Presley har ingen träning alls. När han ger sig in i något seriöst, en större typ av sång, kommer vi att få reda på om han är en sångare. Han har en naturlig, djurisk talang.” När Presley för sin del återigen fick frågan om Sinatras tidigare kommentarer om rock and roll var han lika vänlig mot Sinatra: ”Jag beundrar mannen… Han är en stor framgång och en bra skådespelare”.