Elvis Presley 1959 szeptemberében találkozott az akkor alig több mint 14 éves Priscillával Németországban. Presley az előző évben vonult be a seregbe, és Fort Hood-i kiképzése után a németországi Friedbergbe vezényelték. A Király szentül hitte, hogy énekesi karrierjének a katonaság a végét jelenti majd – attól függetlenül, hogy a rajongók közlegényként is ugyanúgy követték minden lépését. Ismerősei beszámolói szerint Presley kimondottan depressziós időket élt meg: 1958 nyarán édesanyjánál hepatitiszt diagnosztizáltak, a betegség pedig szinte hetek alatt elvitte az asszonyt. Fellépéseinek hiánya valamint imádott édesanyja elvesztése után Elvis rákapott az amfetamin-származékokra – a szerektől haláláig nem szabadult.
Priscilla a nevelőapjának köszönhetően került Németországba – Paul Beaulieu-t az amerikai légierő kapitányaként 1957-ben vezényelték Wiesbadenbe. A fiatal lány végig kívülállónak érezte magát az idegen országban, ráadásul a nyelvet sem beszélte, így egyetlen szórakozási lehetőségként az Eagles Clubba, az amerikai katonák törzshelyére kezdett járni. Priscilla szinte minden nap megjelent a klubban iskola után – így ismerkedett meg a légierő egy fiatal tisztjével, Currie Granttel. Grant volt az, aki felajánlotta a lánynak, hogy bemutatja Presleynek – Priscilla először alig volt hajlandó elhinni, hogy a férfi egyáltalán ismeri a sztárt, később pedig arra kérte Grantet, hogy személyesen is meggyőzze a szüleit, hogy az este alatt mindenki „úriember” lesz.
A nagy találkozásra 1959. szeptember 13-án került sor Bad Nauheimben. A parti résztvevő később bevallották, a Király végig úgy viselkedett a sokkal érettebbnek kinéző Priscilla mellett, mint egy félénk kamasz. Presley volt az, aki a parti végeztével hazafuvarozta a lányt – a Beaulieu-szülők legnagyobb felháborodására, akiket csak hosszú heteken át tartó könyörgéssel és ígérgetéssel lehetett rávenni, hogy egyetlen lányukat ismét elengedjék a sztárral.
Elvis és Priscilla rendszeresen találkoztak, egészen 1960 márciusáig, amikor Presleyt visszavezényelték az Államokba, és leszerelték a seregből. A tinédzser bakfist elárasztották a rajongói levelek és interjú kérelmek, Priscilla viszont meg volt győződve róla, hogy bimbózó kapcsolata a Királlyal véget ért (pláne azután, hogy a lapokat elárasztották az Elvis és Nancy Sinatra románcáról szóló pletykák).
A pár csak 1962-ben találkozott újra, amikor Priscilla szülei beleegyeztek, hogy a lány két hétre az Államokba utazzon a sztárhoz – persze csak azután, hogy Elvis megígérte, nem marad majd kettesben a 17 éves lánnyal. A szülők csak egy évvel később engedték meg, hogy Priscilla végérvényesen visszaköltözhessen az Államokba – azzal a feltétellel, hogy lányuk az érettségiig Elvis apjánál és nevelőanyjánál lakik majd, és a helyi katolikus lányiskolába jár. Pár héttel a megérkezése után azonban Priscilla összeköltözött a sztárral.
Elvis a seregből való leszerelés után fejest ugrott a filmezésbe – fiatal kedvesét azonban nem volt hajlandó magával vinni Hollywoodba, mondván a lány csak unatkozna, neki meg nem lenne ideje foglalkozni vele. A következő években Elvis számos filmbéli kolléganőjével kezdett viszonyt – Priscilla számon kérő kérdéseire azonban csak annyit válaszolt, a lánynak nem kéne minden ostobaságot elhinnie, amit a filmek promózása miatt az újságban leírnak.
A páros 1967. május 1-jén házasodott össze Las Vegasban. A mindössze nyolcperces ceremóniát Nevada állam legfelsőbb bíróságának egy bírája, David Zenoff vezényelte le. A polgári szertartást sajtótájékoztató követte, majd egy szolid fogadás, nagyjából 100 meghívott vendéggel. Elvis és Priscilla ezután Palm Springsbe utazott egy gyors nászútra, majd május végén Gracelandben tartott egy újabb szertartást – azoknak a barátoknak, akik nem tudtak részt venni a vegasi lagzin.
Az esküvő körülményeivel kapcsolatban a mai napig számos pletyka kering: egyesek szerint Priscilla apja ’66 karácsonyán felhívta Elvist, és közölte vele, ha nem veszi el a lányt, vádat emeltet ellene, mivel szexuális célzattal államhatárokon vitt át egy kiskorút. Mások szerint maga Priscilla volt az, aki ultimátumot adott az énekesnek – azaz vagy elveszi, vagy a nő kitálal amfetamin- és nyugtatófüggőségéről a sajtónak. A házasságot Elvis menedzsere, Tom Parker is szorgalmazta, aki féltette a sztár karrierjét – mivel pontosan emlékezett rá, hogy mi történt, amikor Lerry Lee Lewisról derült ki, hogy egy kiskorúval él házasságon kívüli kapcsolatban.
A páros egyetlen gyermeke, Lisa Marie Presley 1968. február 1-jén született, napra pontosan kilenc hónappal szülei esküvője után. Priscilla később maga vallotta be, hogy nagyon felzaklatta, amikor kiderült, hogy gyermeket vár. Attól félt ugyanis, hogy a korai terhesség miatt akaratlanul is eltávolodik majd a férjétől, akinek nőügyei miatt még mindig rendszeresen állt otthon a bál.
Priscilla a kislánya születése után lépett először félre – Elvis sűrű vegasi menetrendje és turnéi pedig odáig vezettek, hogy 1970-re a pár teljesen elhidegült egymástól. Priscilla 1985-ben megjelent „Elvis és Én” című könyvében arról is beszámolt, hogy férje a saját bevallása szerint „sosem volt képes olyan nővel szexuális kapcsolatot létesíteni, akinek gyereke volt.”
Elvis és Priscilla 1972 februárjában különköltöztek, augusztusban pedig beadták a válókeresetet. A vagyoni kérdések miatt a válást csak több mint egy évvel később, 1973. október 9-én mondták ki. Noha Priscilla saját bevallása szerint végig arra törekedett, hogy a megállapodás híven tükrözze, szerelemből, nem pedig pénzért házasodott, ügyvédei később meggyőzték, hogy egy Elvis kaliberű sztár sokkal többet is megengedhet magának, amikor exnejéről és egyetlen gyermekéről van szó.
A tárgyalóteremből a páros kéz a kézben távozott, Priscilla pedig megígérte, hogy Elvis akkor láthatja a lányát, amikor csak akarja. Priscilla a válás ellenére is rendszeresen megjelent a sztár fellépésein, sőt nem egyszer az is előfordult, hogy Elvis aktuális barátnőit tanácsokkal látta el azzal kapcsolatban, hogyan viseljék gondját a Királynak. Közeli barátjuk, Larry Geller később úgy nyilatkozott – Presley egy idő után “sokkal inkább tekintett húgaként Priscillára, mint az exnejeként“.
