The tracks were originally recorded in 1982 for a planned album release on the Columbia Records subsidiary label, Priority Records, under the title Johnny Cash - Gospel Singer. This album was cancelled when parent CBS Records shut down Priority, and the tracks remained unreleased until issued as Believe in Him by Word records.
It is notable as the first album of original material to be released by Cash after leaving Columbia Records though, as noted, he originally recorded the tracks for the company. He subsequently signed with Mercury Records.
In 2012, it was released entirely on CD for the first time as part of Bootleg Vol 4: The Soul of Truth, with a different running order which reflected the originally planned running order for the cancelled Johnny Cash - Gospel Singer, and with the addition of four previously unissued outtakes from the recording sessions.