All the Way was recorded in four separate recording sessions at the Bradley Film and Recording Studio, beginning on August 16, 1960 and ending on May 21, 1961. The album contained twelve tracks of material, seven of which were cover versions of previously recorded songs. The album's cover versions included "Kansas City", first recorded by Little Willie Littlefield. It also included a cover version of Ray Charles's "Talkin' About You" and "On the Sunny Side of the Street". Songwriter Ronnie Self, who had previously written other songs by Lee, co-wrote the song "Eventually" for the album. Allmusic's Richie Unterberger praised the album's production, calling it a "pretty good record" and "certainly well produced". Overall, Unterberger gave the album three and a half out of five stars, explaining that while he felt the album was "pretty good", he said that it seemed to "showcase versatility", like "many albums of its time". Unterberger commented, "It seems a little strange to apply the adjective "overlooked" to a singer as popular as Lee was at this time, but the album, like so much of her early-'60s work, is further evidence of her underrated skills as a rock and pop singer. And it was appreciated by listeners at the time, the album making the Top 20, even if most of the songs are unfamiliar today even to many Brenda Lee fans."All the Way was released originally as an LP record, containing six songs on each side of the record. The album was reissued on a compact disc in both the United Kingdom and Russia.
All the Way spawned its lead single in June 1961 entitled "Dum Dum". The song became Lee's seventh consecutive Top 10 hit on the Billboard Hot 100, peaking at #4, while also reaching #22 on the UK Singles Chart. The single's B-side "Eventually" also gained significant radio airplay and peaked at #56 on the Billboard Hot 100 around the same time of the single's release to radio.All the Way was officially released on August 7, 1961 on Decca Records and peaked at #17 on the Billboard 200 albums chart, her first album that year to peak within the Billboard 200 Top 20. The album also became Lee's first album to chart in the United Kingdom, peaking at #20 on the UK Albums Chart.