After the release of their previous album Truth, by the end of 1968 drummer Micky Waller was replaced by Tony Newman, as Jeff Beck wanted to take the music in a heavier direction and he viewed Waller as more of a finesse drummer in the style of Motown. Pianist Nicky Hopkins, who had also played on Truth, was asked to join the band full-time for their work in the studio.
Recording sessions for the album took place over six days in April 1969 - the 3rd, 6th, 8th, 10th, 11th and 19th. Two covers of Elvis Presley tunes were chosen, "All Shook Up" and "Jailhouse Rock", as well as an instrumental by and prominently featuring Hopkins. The remaining four tracks consist of band originals, with the instrumental "Rice Pudding" ending the album with a hard edit mid-song. The cover features a reproduction of Belgian surrealist artist René Magritte's The Listening Room. On the back cover to the original vinyl issue, beside "Beck-Ola" is written the tag "Cosa Nostra", Italian for "Our Thing".
Following the sessions for this album, the Jeff Beck Group toured the United States. They were scheduled to play Woodstock and are listed on posters promoting the festival, but by then internal friction had reached the breaking point and both Ronnie Wood and Rod Stewart were out of the band. Stewart and Wood would join the Faces in 1969, while Hopkins played Woodstock with Jefferson Airplane and would tour with The Rolling Stones in 1972. Beck himself would be out of commission by December due to an automobile accident.
Upon initial release, Beck commented on the album cover the impossibility of coming up with anything original, and that Beck-Ola indeed was not. Although a short album at half an hour, along with its predecessor it is regarded as a seminal work of heavy metal due to its use of blues toward a hard rock approach and the squaring off of Beck's guitar against Stewart's vocals, duplicated the same year by Beck's confederate Jimmy Page with his singer Robert Plant in Led Zeppelin.
On 10 October 2006, Legacy Records remastered and reissued the album for compact disc with four bonus tracks, all of which had been previously unreleased. Included were two early takes of the Presley covers, one done at Abbey Road Studios in January, a jam on "Sweet Little Angel" by B.B. King done the previous November with the Waller edition of the band, and a song intended as a single by producer Mickie Most but never issued.