"Elvis is Back" was the title of the first album issued after Elvis's release from the army in March 1960, and the title said it all.  Elvis hadn't recorded any new material for nearly two years and RCA was anxious to get something on the market.  After his train ride home, he had little more than a week to relax in Memphis and then was bussed to Nashville for two days of recording on March 20th and 21st.  Within two days of the session, "Stuck on You" / "Fame and Fortune" was released as a new single.  Elvis then took a break from recording to travel to Miami to tape a television special with Frank Sinatra.  He performed his new single and sang a duet with Sinatra – Presley's "Love Me Tender" and Sinatra's "Witchcraft."  Then it was back to the studio in Nashville for three more days (April 3 – 5).  From those March and April sessions twelve songs were selected for the "Elvis is Back" album (the single, "Stuck on You" was not one of the twelve).  The album was released on April 8th.  On May 12th, the Sinatra special was aired by CBS and attracted a high rating (41.5%) which Sinatra's previous specials had failed to do.

By the end of April, "Stuck on You" was the number one single on Billboard and "Elvis is Back" reached #2 on the Billboard album chart in May. In August, the single "It's Now or Never" would reach the top of the chart. That was followed up the charts to the top by "Are You Lonesome Tonight?"  In November, Elvis's first post-army movie was released, "G.I. Blues" – it reached #2 on Variety's box office chart.  The soundtrack album (recorded in April and May in California) went to #1 on Billboard.  By the end of 1960 there was no doubt that not only was Elvis back, but he was bigger than ever.

But behind the success of the television special, the movie, and the recordings there was evidence that things were changing.  A remake of the Italian song, "O Solo Mio, "It's Now or Never" was a clear departure from most of Elvis's previous hit records and "Are You Lonesome Tonight" was a traditional ballad which only "Love Me Tender" rivaled.   It was no accident that Colonel Parker had arranged to have Elvis's first post-army appearance be with Frank Sinatra.  The intent was to present Elvis as more acceptable to a more mature audience; and some believed that the pairing was also a suggestion that Elvis would be the heir to Sinatra's stature as the business's leading vocalist.  While "Stuck on You" was cut from the same rock-a-billy cloth as earlier Elvis hits ("All Shook Up" for example), the "Elvis is Back" album presented a variety of genres.  Colonel Parker had seen Elvis's army duty as a way to gain entry to the adult market and the performances of 1960 had capitalized on that opportunity.

The momentum of Elvis's career in 1960 would continue into 1961.  As the calendar turned to January 1961, "Are You Lonesome Tonight" was in its sixth week at #1.  Elvis's next release, which had been recorded in Nashville in October 1960, "Surrender," also went to the top for two weeks in March.  Elvis had four other top ten songs in 1961:  "Feel So Bad" (#5), "Little Sister" (#5), "His Latest Flame (#4), and at the end of the year, "Can't Help Falling In Love" (#2).  Things would slow a little in 1962 as only "Good Luck Charm" would make it to #1, with "She's Not You" (#5) and "Return to Sender" (#2) also making the top ten. Part of the reason for the decline in record production in 1961 and 1962 was Elvis's focus on his movie career.  Including "G.I. Blues," seven Elvis Presley movies debuted between June of 1960 and December of 1962.

Indeed, Elvis was back, but the post-army Elvis was different.  The "Hillbilly Cat" of 1956 had been replaced with a more pop version of rock and roll.  Some saw the new Elvis as a "sellout," forsaking his rock and roll roots to seek financial reward.  The money was certainly there as all four of his first releases went to number one.  But it is probably unfair to label Elvis's change in music direction as a betrayal of his true calling.  If we look back at the beginning, Elvis's statement to Marion Keisker at the Memphis studio in 1954, "I don't sound like nobody" might have been as much a declaration of musical diversity as it was a proclamation of a dawning of a new musical era.  After all, much of his first recording sessions were covers of Dean Martin tunes and country ballads.  Keisker's initial notation that he was a "good ballad singer" hardly foretold what would emerge as "Elvis the Pelvis."  In evaluating his music, Elvis himself said, "I like to sing ballads the way Eddie Fisher does and the way Perry Como does.  But the way I'm singing now is what makes the money." To be fair, the perceived change in Elvis was reflected in other artists of the early 1960's.  Bobby Darin made a number one hit out of the jazz influenced "Moritat (Theme from the Three Penny Opera)" – "Mack the Knife."  Ricky Nelson, who followed Elvis down the rockabilly road, made "Travelin' Man" a number one song.  Ray Charles had turned to a country sound to produce "I Can't Stop Loving You."  Neil Sedaka's number one, "Breaking Up Is Hard To Do" would fit nicely into the category of "bubblegum" rock.  So if Elvis was "selling out," he was not alone.  The truth was that rock and roll had evolved from its R&B / Country roots into more of a pop sound.  And Elvis was showing himself to be quite comfortable in the new era.  That would soon change; for him and many other rock and roll stars of the early 1960's.