In September 1975, "Over My Head" was released as the lead single from the LP album entitled Fleetwood Mac. It was the band's first song ever to achieve 'hit' status in the United States by appearing on the Billboard Hot 100 Singles Chart (#20 in early 1976). Its success helped the group's eponymous 1975 album to sell eight million copies.
McVie has stated that she composed the song using a portable Hohner electric piano in a small apartment in Malibu, California, where she and then-husband John McVie (Fleetwood Mac's bassist) resided after completing a concert tour to promote the previous album Heroes Are Hard to Find. The words of the song seem—though McVie has never confirmed this—to refer to her troubled marriage, which would end in divorce in 1976.
The 45 RPM single version of the song—released for radio airplay—was a remixed, edited version that differed noticeably from the version on the Fleetwood Mac album. This version is easily distinguished by a cold start (versus the fade-in intro on the LP version), louder guitar strums in the choruses, and less ensemble vocal work overall. In addition, whereas the single version fades during its 3-bar instrumental outro, the album version tape-loops it to 6-bars upon fade out. Finally, while the album version has relatively wide stereo soundstage, the single version is mixed very narrowly (essentially mono) with stereo reverberation effects on some bongo passages and select guitar flourishes. It is this remixed/edited version that is included on the compilation album The Very Best of Fleetwood Mac. The single version is also available as a bonus track on the 2004 remastered CD release of the Fleetwood Mac album.