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. The track was written by Jill Jones, and produced by David Z. and Jill Jones. Prince appears on the track as a musician, having recorded a guitar solo and possibly other unidentified overdubs for the song.
While specific recording dates are not known, basic tracking took place at some point in 1986, most likely at Sunset Sound, Hollywood, California. Prince recorded his 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).