77 Bleeker St. was released as the b-side of Jill Jones's single Mia Bocca, the first single from her first and only Paisley Park Records album Jill Jones, released seven weeks prior to the album. Prince appears on the track as a musician, having recorded a guitar solo and possibly other unidentified overdubs for the song. It has long been thought that the song was written by Jill Jones and produced by David Z. and Jill Jones. But the credits at the ASCAP, which were seemingly changed after Prince’s passing, indicate that this song was composed by Prince and Jill Jones. The song is registered at ASCAP under the title 77 Bleeker Street.
While specific recording dates are not known, basic tracking took place at some point in 1986, most likely at Sunset Sound in Hollywood, California. Prince recorded some overdubs in mid-January 1987 at Prince's Galpin Blvd Home Studio in Chanhassen, Minnesota after completion of the Sign O' The Times album (during the same set of sessions that produced Come Home and La, La, La, He, He, Hee).