Anotherloverholenyohead is the fourth and final single (third and final in North America) to be released from Prince's eighth album Parade, the third album credited to Prince and the Revolution, and was released three months after the album's release. The b-side, Girls & Boys, was also taken from the album Parade.
In the UK, where Girls & Boys was released as a single, the b-side instead was I Wanna Be Your Lover, taken from Prince's second album Prince. The 12" version contained an extended version of Anotherloverholenyohead, unavailable elsewhere.
The single reached number 63 on the US Billboard Pop Chart, and number 18 on the Billboard R&B Chart.