Anmeldelserne er ikke overvældende, der antyder at Elvis ikke passer til Vegas publikummet. Selve hotellets showroom var opbygget som en slags amfiteater opdelt med borde sat i 12 hestesko formede opstillinger. Las Vegas var i 1956 alt andet end hvad Elvis var; det var et voksens publikum og let underholdning. De var ikke kommet til Vegas for at høre ungdommelig musik, men nærmere for at komme væk fra det hele derhjemme – og for første gang siden Elvis startede sin karriere, kunne han rent faktisk høre hvad bandet spillede og hvad han selv sang. Elvis prøvede at inkorporere nogle små jokes i sin optræden, som han havde lært fra Dewey Phillips i Memphis. Selvom Las Vegas ikke var klar til Elvis, kunne han dog godt lide byens liv, men lige lidt hjalp det på publikums modtagelse af hans optrædener.

Elvis blev dog mere og mere sikker efterhånden som han spillede de forskellige aftener, så det var ikke fordi han ikke kunne lide det, men responsen var ikke som ved de normale shows.

Engagementet på New Frontier slutter med et show 6. maj og Elvis rejser et par dage efter tilbage til Memphis, hvor han endelig kan nyde et par dage hjemme i sit nye hus på Audubon Drive.  Han får dog også mulighed for at komme forbi den lokale avis, hvor han fortæller at han rigtig godt kunne lide Las Vegas og gerne vil tilbage, når lejligheden byder sig. Imens han er hjemme i Memphis, kommer han også forbi Dewey Phillips’ radioshow for at hilse på, inden han lørdag flyver til Minneapolis hvor han og bandet indlogerer sig på to forskellige hoteller.  Tiden hvor de altid har boet sammen, er ved at ændre sig.

Søndag den 13. maj skal de optræde i St. Paul, Minnesota kl. 15. Showet er som sædvanligt arrangeret af Tom Parker, men fra denne dag og fremover vil der ikke være nogen til stede på scenen som kan opfattes som en rival til Elvis. Tom Parker insisterer og står fast på dette format, på trods af at både RCA og William Morris gerne vil have et show, som appellerer lidt bredere.  I praksis betyder det, at der kan godt være opvarmning af forskellig karakter, men ingen optrædende som skal konkurrere med Elvis’ optræden. Senere samme dag optræder han også i Minneapolis ved en koncert kl. 20.

I dette nye setup med Elvis som absolut hovedattraktion og med opvarmning fra forskellige typer optrædende, får Elvis hjælp fra en promoter ved navn Al Dvorin, som er fra Chicago, som hjælper med at skaffe optrædende som kan fungere som opvarming. Han hjælper også med at sætte showet op i LaCrosse, Wisconsin den næste dag.

Selvom Elvis’ musik er blevet meget mere udbredt og ikke mindst anerkendt i forhold til i starten, så er det ikke alle der bryder som om den og endnu mindre om Elvis’ sceneoptræden, som de mener er en yderst seksuel fremtoning på scenen. Det kommer så vidt, at der bliver sendt brev til chefen for FBI, Edgar Hoover fra den lokale avis i LaCrosse, efter de to shows denne aften. Elvis er begyndt at blive bemærket, udover det rent regionale.

Dagen efter, d. 15. maj, er Elvis tilbage i Memphis hvor han optræder på Ellis Auditorium, hvor han optræder i mørke bukser, hvid skjorte og grøn jakke. Denne gang er Elvis øverst på plakaten før Hank Snow. Det er Bob Neal som er hovedmanden bag dette show og han annoncerer ved showstart at Elvis også vil optræde 4. juli, på nationaldagen.
Den kommende dag fortsætter han med at optræde i lokalområdet med en koncert i Little Rock, Arkansas. Ved den lejlighed bliver han spurgt om hvilken af hans sange, der er hans favorit. ”I Was The One”, lyder svaret. Næste dag flyver han til Springfield i staten Missouri for at optræde på Shrine Mosque. Resten af bandet vælger at køre i bil dertil, hvor de til lejligheden har lånt Elvis’ cadillac.
Fredag aften optræder Elvis ved to koncerter i Wichita, Kansas kl. 19 og 21:30, hvorefter de fortsætter mod Lincoln, Nebraska, hvor han giver en enkelt koncert. Der er stadig megen snak om den dårlige indflydelse hans musikstil har på de unge, hvortil han svarer at han startede med at synge gospel og kommer fra et kristent hjem. Søndag optræder han ved to koncerter i Omaha, Nebraska kl. 15 og 20, hvorefter han flyver mod Topeka, Kansas den følgende dag for at spille. Over de næste 8 dage bevæger de sig fra Iowa, Missouri og Ohio og optræder ved i alt 11 koncerter. Ved en af koncerterne i Kansas City, er det ved at gå helt galt da der opstår tumult, Bill Blacks bass bliver smadret og D.J. Fontana bliver skubbet ind i resten af orkestret, Elvis selv flygter ud i en bil efter omkring 20 minutter på scenen.