Kirk Kerkorian, presidente da Trans International Airlines e proprietário do Caesars Palace, foi o homem por trás do International Hotel, construído em 1969, um edifício de 30 andares e 1.510 quartos, que custou 50 milhões de dólares. Era o maior hotel do mundo. O hotel abriu em 2 de julho de 1969. Possuía um salão de espetáculos com capacidade para 2.000 pessoas, o maior de Las Vegas. Foi construído no local de uma pista de corridas desativada. Foi considerado um projeto arriscado construir um hotel tão grande fora da famosa Las Vegas Strip; era necessária uma grande estrela para o salão de espetáculos.
O Coronel Parker não queria que Elvis fosse o primeiro artista a atuar no salão de espetáculos, considerando que o edifício era novo e poderia apresentar problemas. Assim, Barbara Streisand foi a primeira a atuar no salão. O Coronel provou estar certo, e os críticos notaram que alguns elementos do hotel não estavam finalizados quando Streisand atuou. Notaram também que Streisand parecia perdida no enorme palco e passou muito tempo a cantar para a orquestra em vez de para o público. O hotel também tinha um teatro com 500 lugares onde atuou Peggy Lee. Lee recebeu críticas mais favoráveis.
Entretanto, Elvis estava ocupado a montar uma nova banda que contaria com o guitarrista principal James Burton, que tocara para Ricky Nelson nos anos 50 e era, na altura, um dos músicos de sessão mais respeitados na indústria de gravação, Jerry Scheff no baixo, Ronnie Tutt na bateria, John Wilkinson na guitarra rítmica, Larry Muhoberac ao piano (Elvis conheceu-o em sessões de gravação de bandas sonoras, mas seria substituído por Glen D. Hardin em 1970), mais dois conjuntos de cantores de apoio, The Imperials Quartet e The Sweet Inspirations. As Sweet Inspirations incluíam a mãe de Whitney Houston, Cissy. Whitney diria anos mais tarde, depois de ir com a mãe a Las Vegas ver Elvis: “Na verdade, não se CONHECE o Elvis, olha-se para o Elvis. Ele era incrível de se ver, e foi um momento que nunca esquecerei.” Whitney tinha seis anos na altura. A banda principal seria então reforçada pela orquestra residente do International Hotel, liderada por Bobby Morris (Joe Guercio e a sua orquestra juntar-se-iam a Elvis a partir de 1970).
Os ensaios começaram em Los Angeles a 18 de julho de 1969, antes de o grupo partir para Las Vegas a 24 de julho. Foram aprendidas cem canções, incluindo êxitos de Elvis, gravações recentes e canções que Elvis queria cantar de outros artistas. No que diz respeito aos êxitos dos anos 50, Elvis queria que fossem reinventados, dizendo à banda para não tentar tocá-los como tinham sido tocados na altura. Elvis queria um som fresco e contemporâneo. A nova banda trabalhou arduamente e, imediatamente, todos se conectaram com Elvis. Ronnie Tutt diria mais tarde: “Ele tinha tanto carisma – quero dizer, o tipo tinha-o. E ao conhecê-lo e olhar nos seus olhos, simplesmente nos conectámos. E a partir desse momento em particular, eu observava-o, e observava os seus olhos, observava os seus movimentos, observava tudo o que ele fazia. E como ele me disse: ‘O que me impressionou em ti, Ronnie, foi o facto de não estares a olhar em volta a fazer a tua coisa, estavas a observar-me. Tudo o que eu fazia, tu captavas e acentuavas’.” Elvis e a banda tiveram uma semana de ensaios com a orquestra residente antes da noite de estreia de Elvis. O Coronel também esteve ocupado, a preparar toda a sua mercadoria.
A noite de estreia foi a 31 de julho de 1969. Haveria apenas um espetáculo nessa noite, o jantar, às 22:30. Durante as quatro semanas seguintes, Elvis faria dois espetáculos por noite, um espetáculo ao início da noite, bem como o jantar, cinquenta e sete atuações no total. Entre 31 de julho de 1969 e 12 de dezembro de 1976, Elvis atuaria 636 vezes no hotel; todas as atuações esgotaram, quebrando todos os recordes de público.
Todos queriam ver a noite de estreia de Elvis a 31 de julho de 1969. Entre o público estavam os atores Cary Grant e George Hamilton, o artista Sammy Davis Jr., o compositor Burt Bacharach, os cantores Petula Clark, Dionne Warwick, Paul Anka e a co-estrela de Viva Las Vegas, Ann-Margret.
À medida que a noite de estreia se aproximava, Elvis ficava cada vez mais nervoso. Isto não era como o pequeno público de algumas centenas de pessoas que foram convidadas para a gravação do programa de TV. Era um público que também incluiria membros da imprensa mundial. Elvis sabia que tinha de acertar.
Elvis subiu ao palco num fato preto de duas peças, folgado, inspirado num Kimono de karaté. A partir do momento em que entrou em palco, o público levantou-se a aplaudir. Elvis dirigiu-se ao microfone, acenou ao público, agarrou o microfone e atacou "Blue Suede Shoes". A reação do público nunca diminuiu. Na primeira parte do espetáculo, Elvis interpretou os seus primeiros êxitos, "Heartbreak Hotel", "Don’t Be Cruel", "Jailhouse Rock", "All Shook Up", antes de passar a interpretar êxitos mais recentes e gravações das sessões americanas, incluindo "Memories", "In the Ghetto" e "Suspicious Minds". Pelo caminho, trouxe um banco de guitarra e tocou "Are You Lonesome Tonight?" usando a sua Gretsch elétrica. Elvis acreditava que, quando as pessoas iam a um concerto ao vivo, queriam ver um espetáculo e exigiam mais do que podiam ouvir em disco, por isso misturava as coisas e incluía "Yesterday" dos Beatles, "Runaway" de Del Shannon e "I Can’t Stop Loving You" de Ray Charles. Terminou com "Can’t Help Falling in Love", que se tornaria uma tradição para o resto da sua carreira.
As críticas foram extasiadas. O London Evening Standard escreveu que ele era "sensacional – melhor do que qualquer um de nós poderia alguma vez ter imaginado." A Newsweek escreveu: "Há várias coisas inacreditáveis sobre Elvis, mas a mais incrível é a sua longevidade num mundo onde carreiras meteóricas se desvanecem como estrelas cadentes."
O guitarrista rítmico John Wilkinson disse que a banda não estava preparada para a reação do público, dizendo: "Eles não se calavam, durante toda a primeira música continuavam a gritar e a aplaudir, não se fartavam dele." Mac Davis, o compositor de "In the Ghetto", disse: "Nunca vi nada assim na minha vida."
