"מלון הלבבות השבורים" היה הלהיט הראשון של אלביס פרסלי שהגיע לפסגת המצעד האמריקאי, באביב 1956. עד חורף 1958, 9 סינגלים נוספים שלו כבשו את ראש המצעד. אלביס הפך למלך הרוקנרול ולכוכב הגדול ביותר באמריקה. אבל, הפופולאריות העצומה שלו באותם שנים הניעה במקביל גם ויכוח ציבורי גדול שפרץ בחברה האמריקאית: הרוק נחשב בקרב הדור המבוגר יותר ובעיקר בחוגים דתיים כדבר שמקלקל את הנוער ופוגע בערכים השמרניים. ואם כך, אז אלביס הנערץ ע"י הצעירים, הוא מי שגם מוביל אותם לתרבות רעה.
על מנת לשפר את תדמיתו, ולסמן את עצמו כמי שתורם לחברה האמריקאית בדיוק כמו כל אזרח אחר, התגייס אלביס בגיל החובה (21) לצבא האמריקני ושירת שנתיים, בין מרץ 1958 ועד מרץ 1960. הוא גם ויתר על ההצעה שקיבל, לבדר את החיילים ולשיר להם, והחליט לעבור את השירות כחייל מן המניין. מרבית השירות שלו היה כחלק מהכוחות האמריקאיים שהוצבו בגרמניה. קהל המעריצים של אלביס התאכזב כשהבין שאלילם לוקח סוג של "פסק זמן". ההורים ואנשי הדת דווקא שמחו על הגיוס של אלביס וירידתו מהבמה, מכיוון שזה ישים סוף ל"קלקול הנוער". אבל לאלביס ולמנהלו היו תכניות אחרות.
היעדרות של שנתיים מעולם הבידור הציבה בפניו סיכון גדול. אופנות מחלפות מהר והיעדרות שכזו עלולה להשכיח את אלביס בקרב הציבור. "אם אתה לא בתודעה, אתה לא קיים" אומר משפט אמריקאי מפורסם (Out of sight, out of mind). אבל אז החליט האמרגן הממולח שלו, קולונל טום פארקר, לעשות מהלך שיווקי שישמר את אלביס בתודעת הציבור. המחשבה היתה שלמרות שאלביס לא יוכל להופיע או לככב בסרטי קולנוע, יש דרך אחת שתבטיח שהמעריצים לא ישכחו אותו: אלביס יקליט שירים חדשים רבים, ואלו ישוחררו לרדיו, ולרכישה בחנויות התקליטים כסינגלים, אחת ל-3-4 חודשים. כלומר, מוצרים חדשים מאלביס לעיתים תכופות, למרות שהוא שוהה בכלל בגרמניה כחייל. בהנחה שהרדיו ישמיע את הלהיטים החדשים כל הזמן, אלביס יישאר בתודעה של מעריציו. וכך היה.
בין אפריל 1958, כחודש לאחר שהתגייס, ועד יולי 1959, שמונה חודשים לפני שחרורו, שחררה חברת התקליטים שלו RCA חמישה תקליטונים לשוק וכולם הפכו ללהיטים. בין השירים אפשר למצוא את One night, I got stung וגם את I need your love tonight ואת A big hunk of love. המהלך השיווקי הזה הצליח.
בקיץ 1958, חודשים ספורים לאחר הגיוס שלו, דאג קולונל פארקר גם לסרט קולנוע חדש בכיכובו של פרסלי, "קינג קריאול". את הסרט הקדים תקליטון שהפך להיט, Hard headed woman, ואלבום שלם שהוא פסקול הסרט. זה היה האלבום היחיד שאלביס הוציא במהלך אותן שנתיים, אלבום שהוקלט כמובן כולו מראש.
לקראת השחרור הכריז קולונל פארקר על ה"קאמבק" הגדול של אלביס. ואכן, 15 יום בלבד לאחר שחרורו הוא כבר הקליט שני שירים שיצאו על תקליטון אחד, Stuck on you שהפך ללהיט גדול וגם את Fame and fortune. אלבום בשם Elvis is back יצא לשוק זמן קצר לאחר מכן, ואלביס חזר לעניינים. שנת 1960 זימנה לו עוד שני להיטי ענק בכל העולם, It's now or never ו-Are you lonesome tonight. אבל אלו הצליחו גם בזכות הרצף המוזיקלי שנשמר בתודעת הציבור, ושלו דאג קולונל פארקר, למרות שאלביס שירת שנתיים מלאות כחייל בצבא ארצות הברית.
לפי "איגוד הקלטות המוזיקה האמריקאי" נמכרו עד 2019, באמריקה בלבד, 146.5 מיליון עותקים מאלבומיו של אלביס. רק ה"ביטלס" מכרו יותר ממנו. חברת האם שלו, RCA, מעריכה שאלביס מכר בכל העולם למעלה ממילארד וחצי אלבומים בכל הפורמטים (אלבומים וסינגלים), מהם 600 מיליון עותקים בארצות הברית בלבד.
אלביס מת בשנת 1977 בגיל 42 בלבד.