The album version of "Brokenhearted" was recorded in a single take, Brandy remembered during the release of The Best of Brandy in 2005: "There's a funny story behind the recording of that song! I really wanted to go to Six Flags but the producers kept saying, ‘only after you finish recording!' I sang my heart out...I wanted to go to Six Flags so bad! You can hear the passion in my voice!"
The idea for a duet version of the album originally came up while Brandy was on a two-month stint as the opening act on Boyz II Men's national tour in early 1995. Both artists were on the airplane on the way to another city, when Morris got his hands on a copy of Brandy's debut album: "I was listening to her album on the plane and I was like, 'Yo, we should do a duet of 'Brokenhearted'," Wanya told MTV News the following year.
The music video for the single was directed by Hype Williams and filmed inside the Oheka Castle in Spring Hills, New York.[not in citation given] Williams picked the castle because the owner was willing to let them ruin the floors and the walls with water and paint to out the video treatment into practice. "It's basically a dream, because of course this is not reality," Brandy told MTV during the shooting. "I can't afford a mansion right now, so it's like I fall asleep and I dream about doing a duet with Wanya and I'm in this big mansion wearing these grown clothes, big beautiful Whitney Houston-type clothes." Since the water was on the floor, the crew had to wear boots during filming. Actor Donald Faison makes a cameo appearance in the video.