Podpisuje też z  Paramount Pictures od razu aż siedmioletni kontrakt na występowanie w filmach.

Na pokładzie lotniskowca USS Hanckock realizowany jest program sieci ABC z udziałem Elvisa - "The Milton Berle Show".

Właśnie w 1956 roku po kolejnym występie w programie "The Milton Bearle Show", tym razem realizowanym w studiu telewizyjnym, Elvis doprowadza publikę do szaleństwa a jego zmysłowe poruszanie się na scenie oburza całe Stany. Leje się morze krytyki. Telewizja musi pokazywać Presleya wyłącznie od pasa w górę...

Ed Sulivan powiedział kiedyś publicznie, że kogoś takiego jak Elvis nigdy nie pokaże.
Teraz sam o to zabiega. Za trzy występy daje Elvisowi 50 000 dolarów - kwota na owe czasy astronomiczna za wystąpienie w telewizyjnym show.
Ale też jego występy windują wskaźniki oglądalności tego programu do niespotykanych dotąd poziomów...

Kiedy w Tupelo, mieście urodzenia Presleya, zostaje proklamowany Dzień Elvisa Presleya przyjeżdża i daje dwa koncerty na "Mississippi - Alabama Fair and Dairy Show"
To ta sama impreza, na której w wieku dziesięciu lat wystąpił.
Tym razem aby zapanować nad podekscytowaną, głównie żeńską częścią publiki, sceny pilnuje tysiąc żołnierzy Gwardii Narodowej :)

I stało się. Ugruntowały się narodziny nowego symbolu kultury amerykańskiej młodzieży. Odtąd nic nie będzie już tym, czym było wcześniej... Narodził się kult Elvisa. Świat oszalał. A przemysł pamiątkarski wpadł na pomysł żeby to wykorzystać.

1958-1960. Elvis w wojsku. W końcu jest w Europie. Zwiedza Monachium i Paryż. A na jednym z przyjęć w swoim (wynajętym obok bazy) domu poznaje Priscillę Beaulieu.
W tym czasie Colonel Parker podtrzymuje popularność Elvisa w Stanach wypuszczaniem na rynek płyt z piosenkami wcześniej nagranymi. Rynek gadżetów ma się nieźle. Sprzeda się każdy koszmar byle miał napis "Elvis".

W końcu Elvis wraca do siebie. Jest sierżantem i posiadaczem czarnego pasa w karate.
Nagrywa nowe płyty i występuje w kolejnych filmach. Pierwszym jest "GI Blues".
Ścieżka dźwiękowa z tego filmu trafia na listę Bilboardu i jest na niej aż 111 tygodni - pod tym względem to najlepszy album Elvisa w karierze...

Jeszcze ciekawszy jest kolejny film Elvisa - "Flaming Star". W filmie tym Presley gra syna białego ojca i Indianki rozdartego między dwiema kulturami.
W RPA film ten otrzymał zakaz rozpowszechniania i wyświetlania ze względów... rasowych. 

W 1961 roku Elvis daje pierwszy koncert na Hawajach. Corocznie Elvis wspiera ze swojej strony średnio do 50 różnych takich przedsięwzięć. Koncert charytatywny mający pomóc uzyskać fundusze na budowę pomnika poległym marynarzy USS Arizona.
Same Hawaje bardzo przypadły Elvisowi do gustu  - teraz jest tu częstym gościem. Jest też film "Blue Hawaii". Bardzo dobrze oceniany przez krytykę.