The album was recorded on September 19, 1955 in the gothic-revivalist styled assembly hall of Sunset School (now Sunset Arts Center) in Carmel-by-the-Sea, California, a welcoming space being used as part of local promoter Jimmy Lyons' "Sunset Series", this series in turn laying the groundwork for the beginnings of the Monterey Jazz Festival. From nearby Fort Ord military base servicemen were bused to join the enthusiastic and receptive audience at this Erroll Garner Trio gig. Accompanying Garner were bassist Eddie Calhoun and drummer Denzil Best. According to Columbia Records and its owner, Sony Music Entertainment, the acoustics were poor and the piano somewhat out of tune. The balance of instruments on the recording was also poor; the bass and drums were receded.
There was no plan to record the concert officially. The release came about because Garner's personal manager, Martha Glaser, spotted backstage that a tape recorder was running. The recording was being made by a recording engineer for the Armed Forces Radio Network, "a jazz fan and scholar named Will Thornbury, strictly for the enjoyment of himself and his fellow servicemen". Glaser took the tape, put it into album form, and then played it for the head of Columbia Records' jazz division, George Avakian, who decided to release it. The original LP was released by Columbia as catalog number CL 883; an "electronically rechanneled to simulatestereo" version, with catalog number CS 9821, was issued in 1969.
AllMusic awarded the album a maximum five stars, observing it is "arguably the finest record pianist Erroll Garner ever made".The Penguin Guide to Jazz gave it 3½ stars out of 4 (and added it to the book's suggested Core Collection), asserting that: "Concert by the Sea is essentially neither more nor less than a characteristic set by the trio". Critic Scott Yanow's opinion is: "this is the album that made such a strong impression that Garner was considered immortal from then on."
On September 18, 2015, Sony Legacy released the album in an expanded box set version titled The Complete Concert by the Sea. Its three compact discs include the unedited full concert on discs one and two, with 11 tunes that did not appear on the original album, the original release remastered, and a 14-minute post-concert interview on disc three. The New York Times wrote: "the set will double the available music from the concert, shedding new light on Garner in what is often considered his finest hour."
The release of The Complete Concert by the Sea is part of the Erroll Garner Jazz Project, a major new archival and musical celebration of Garner. Additionally, Martha Glaser's longtime agent and manager donated a large trove of Garner material from Glaser's estate to the University of Pittsburgh Library System (both Garner and Glaser were from Pittsburgh), with the promise of more new Garner music to come.