Flere forfattere har skrevet, at “Elvis havde travlt om aftenen med forskellige kærester”, eller at hans “liste over one-night stands kunne fylde et helt bind”. Skuespillerinden Anne Helm har for eksempel udtalt, at Presley “virkelig kunne lide sex”. “Jeg havde det sjovt”, siger hun. “Og det var noget særligt.” Hun har endvidere hævdet, at Elvis elskede den flæseagtige, gule baby-dukke-natkjole, som han havde købt til hende, og at han gav hende piller efter at have haft sex med hende.
Det er uklart, om Presley faktisk havde samleje med de fleste af de kvinder, han datede. Hans tidlige veninder Judy Spreckels og June Juanico siger, at de ikke havde noget seksuelt forhold til Presley, og der var flere kvinder, som Elvis hurtigt omgik seksualiteten helt og holdent, og som han fandt sig til rette i behagelige venskaber. Spreckels, sangerinden Betty Amos, frisør Patti Parry og andre, der stod Presley nær, udfyldte alle søsterroller for Elvis. Selv om June Juanico påstod, at hun ikke havde noget seksuelt forhold til Elvis, sagde hun i et interview til filmen Elvis 1956: “Jeg vil ikke sige, hvad der skete mellem os. Det er personligt.” Byron Raphael og Alanna Nash har udtalt, at stjernen “aldrig ville putte sig selv ind i en af disse piger…” (af en række årsager).
Albert Goldman spekulerede i, at Elvis foretrak voyeurisme frem for normale seksuelle relationer med kvinder. Goldman fortsatte med at antyde, at Elvis under sin militærtjeneste havde “opdaget prostituerede og opfanget den intense frygt for seksuelt overførte sygdomme, hvilket førte til påstande om, at han havde en morbid frygt for seksuel penetration”. Alanna Nash, i sin bog, “Baby, Let’s Play House”: Elvis Presley and the Women Who Loved Him (2010), afslører et behov hos Presley for at spille Pygmalion og far for meget unge piger, som han glædede sig til at gøre om på. Som en sent blomstrende “mors dreng”, hævder hun, var den unge Elvis en fiasko med pigerne og superreligiøs. På grund af frygt for seksuelt overførte sygdomme ville han faktisk ikke gå “ind i” kvinder, han klædte sig aldrig af og var mere interesseret i at se på kunstfærdige tableauer, der ofte involverede fødder.
June Juanico “husker et tidspunkt, hvor hun stod op imod Elvis over for hans bande af følgesvende, som allerede dengang var begyndt at følge ham overalt. Han greb fat i hendes arm, tog hende med ind på badeværelset og erklærede: “Hør, du har så ret, jeg er virkelig ked af det”. Han holdt hende der i fem minutter, hvorefter han gik ud med sit image intakt.” Julie Parrish, Presleys medspiller i Paradise Hawaiian Style, fortæller: “En gang på settet havde jeg virkelig ondt i siden – en bivirkning, tror jeg – og Elvis tog mig op, bar mig ind i sin trailer og lukkede døren. Udenfor ventede holdet og undrede sig, men Elvis var ligeglad med antydningerne. Han lagde sin hånd på min side og forsøgte at helbrede mig.” Playboy-stjernen og skuespillerinden June Wilkinson huskede, at hun “mødte Elvis på settet af King Creole. Han inviterede mig til middag på Beverly Wilshire Hotel. … Derefter gav Elvis mig en rundvisning i sin suite, satte mig på sengen i sit soveværelse og sang for mig i to timer. Det var det hele. Den næste dag … spiste vi middag igen. Han var meget sød, og han var venlig. Han havde mere end sex i tankerne. Han fik mig til lufthavnen til tiden, og vores veje krydsede aldrig hinanden igen.”
Den sanger var dog ikke altid sød og venlig over for kvinder. Da Christina Crawford, Joan Crawfords adoptivdatter, besøgte Presley, så de Bonanza i tv-stuen. “Elvis havde pustet på en cigar … mens Christina kildede ham og lavede sjov med ham og tilsyneladende søgte mere direkte opmærksomhed.” Pludselig, som Buzz Cason fortæller, “smed hun indholdet af sit cocktailglas lige ind i Elvis’ ansigt. … cigaren gik ‘phhhtttttt’, og han sprang op. … Han greb hende i håret. ‘Få den kælling ud herfra!’ skreg han og førte hende mod hoveddøren, mens hun kæmpede for at følge med i det ret hurtige tempo, da han trak i hendes lokker. Der opstod tumult, da ‘drengene’ skyndte sig at hjælpe i forsøget på at forhindre en alt for stor scene.”
Peggy Lipton hævder, at Presley var “praktisk talt impotent” over for hende. Hun tilskrev hans impotens til hans drengerøvsagtighed og store stofmisbrug. Cassandra Peterson, bedre kendt som “Elvira”, siger, at hun kun kendte Presley i én nat, og at de kun talte sammen.
Disse påstande modsiges direkte af kommentarer fra skuespillerinder som Cybill Shepherd, der erkendte sin affære med sangeren og sagde, at hun havde introduceret Elvis til visse elskovsteknikker. Men “de “meget citerede påstande om, at hun lærte ham glæden ved oralsex, bliver betragtet med skepsis af andre elskere af kongen”. I et interview sagde Shepherd, at Presley kyssede hende over hele hendes nøgne krop – men at han nægtede at have oralsex med hende. Hans langsomme ømme kys endte ved hendes navle. Elvis sagde til hende: “Mig og fyrene snakker og, ja, vi spiser ikke fisse.” Hun vidste altid, at deres forhold var dødsdømt, og at de ikke ville holde som par. Hun siger: “Faktum er, at Elvis blev afhængig af speed i hæren. … Så kom det ud af kontrol. Havde jeg lyst til at være sammen med en, der ville have trukket mig ned? Den eneste måde at blive sammen med Elvis på var ved at tage stoffer.”
I sine erindringer omtaler Ann-Margret (Presleys medspiller i Viva Las Vegas) Presley som sin “soulmate”, men der afsløres meget lidt om deres længe rygtede romance, kun at han “i et øjeblik af ømhed” købte hende en rund seng i hot pink farver.
På den anden side datede Elvis mange kvindelige medspillere fra sine film primært af hensyn til reklame. Den 17-årige skuespillerinde Lori Williams og sangeren var for eksempel sammen i et stykke tid “mellem optagelserne af Roustabout og Kissin’ Cousins”. Hun siger, at deres “frieri var ikke en bizar historie. Det var meget sødt, og Elvis var den perfekte gentleman.” Hun hævder også, at Ann-Margret “var hans livs kærlighed”. Betydningsfuldt nok var der en stor reklamekampagne om romancen mellem Elvis og Ann-Margret under optagelserne af Viva Las Vegas i 1963 og de efterfølgende uger, hvilket var med til at øge den unge Hollywood-skønhedens popularitet. Ann-Margret forblev tæt knyttet til Presley resten af hans liv og deltog også i hans begravelse.
De allerfleste bøger (herunder begge Guralnicks bøger) om Presley indeholder detaljer om hans mange romancer og påståede affærer, herunder mange mens han var gift med Priscilla. Det er også blevet rapporteret, at Presley “elskede at kæle for og sutte på kvinders tæer, og de i hans omgangskreds, der fik til opgave at vælge ledsagere til ham, blev ofte bedt om at tjekke pigernes fødder.”
Ifølge Alan Fortas, en football halfback fra hele Memphis, der blev bodyguard og en del af Presleys omgangskreds, “havde Elvis mere brug for nogen at babysitte med end han havde brug for en sexpartner. Han higede efter opmærksomhed fra en person, der tilbedte ham uden truslen om seksuelt pres, ligesom en mor ville gøre det.” Desuden “Elvis blev venner med nogle af de unge piger, der plejede at klynge sig tilbedende i hans indkørsel eller uden for hegnet … Nogle af pigerne var så unge som fjorten år. Fortas sagde, at de var hyppige husgæster, som deltog i hans koncerter som en del af “Elvis’ personlige rejseshow”. Ude i baghaven boltrede de sig med Elvis i Doughboy-poolen og udfordrede ham til konkurrencer i at spytte vandmelonfrø. De smuttede også ind i hans soveværelse … for at deltage i en vild pudekamp. Nogle gange sad de alle sammen med ham i kryds og tværs på sengen og bladrede i hans fan-magasiner eller beundrede hans samling af udstoppede dyr. Ofte lagde de sig alle sammen ned og krammede. Men det, der foregik, var hestespil, ikke forspil.” Derfor skriver Guralnick, at for “de mere erfarne piger var det ikke som med andre Hollywood-stjerner eller endog med andre mere sofistikerede drenge, de kendte”. Selv om de tilbød at gøre ting for Presley, “var han ikke rigtig interesseret. Det han kunne lide at gøre var at ligge i sengen og se fjernsyn og spise og snakke hele natten…”
Dolores Hart var den kvindelige kærlighedsinteresse fra Elvis’ anden og fjerde film, og var hans første kys på skærmen. Hun hævder, at hun ikke havde et intimt forhold til sin medspiller. Fem år efter sin sidste film med Elvis forlod hun Hollywood for at blive benediktiner nonne. Dokumentarfilmen God Is the Bigger Elvis fra 2011 dækker deres forhold.
Anita Wood, en anden pige, som sangerens mor håbede, at Presley på et tidspunkt ville gifte sig med, var sammen med ham, da han steg til superstjernestatus, tjente i det amerikanske militær og vendte hjem i 1960. Hvis han havde planer om at gifte sig med en pige, ville han have, at hun skulle forblive jomfru. Anita Wood boede på Graceland i en periode, men stjernen havde ifølge hans egne ord ikke sex med hende. Hun flyttede ud efter at have konfronteret ham med Priscilla Presley, der dengang var kendt som Priscilla Beaulieu.