The Paul Butterfield Blues Band was the first group to record and release the song commercially, featured as a track on their 1966 album East-West. In addition to Butterfield, musicians to play on the track include Mike Bloomfield and Elvin Bishop. Curiously, no songwriter credit is listed for "Mary, Mary" on East-West.
Run-D.M.C. changed the line "Mary, Mary, where ya' goin' to" to "Mary, Mary, why ya' buggin'". Although Run-D.M.C. replaced Michael Nesmith's original lyrics with a new set of lyrics of their own, Nesmith was the only writer credited on Run-D.M.C.'s single. Run-D.M.C.'s version samples Micky Dolenz singing the title from the Monkees' recording.