His previous gospel album His Hand in Mine had been a solid catalog seller for RCA. While Presley faced difficulty getting radio airplay in the mid-1960s, during that decade radio stations played Christmas music at Christmas-time and religious music at Easter, and Presley's manager, Colonel Tom Parker, was convinced Presley could break through in these niche markets. So, recording sessions were arranged with the purpose of producing a Christmas single and a follow-up LP to His Hand in Mine.
How Great Thou Art would in fact be Presley's first non-soundtrack album recording of new material since Pot Luck with Elvis in 1962, and his first album release not to include any soundtrack recordings since the previous gospel album in 1960. It also introduced producerFelton Jarvis to Presley on the singer's second non-soundtrack sessions since May 1963. Jarvis would continue to work with Presley for the remainder of his career.
As the sessions for the album progressed, Elvis rejected many of the planned songs for which Freddy Bienstock had obtained publishing deals, and began picking favorites of his own and those of the musicians. The five songs in the public domain were credited as "arranged by Elvis Presley" and published by Elvis Presley Music allowing Bienstock to secure the royalties for those selections. In fact, it is likely that an engaged and enthusiastic Presley indeed did the arrangements, as he certainly did with the title song, his months of practice at home on his beloved gospel songs paying off.
"Crying in the Chapel" was released as a single (RCA 47-0643) on April 6, 1965 and reached number 3 on Billboard's Hot 100 chart. "You'll Never Walk Alone" was released as a single (RCA 47-9600) in March 1968 and reached position 90. Its B-side is "We Call On Him".