The band was assembled by Prince from the summer of 1981 to January 1982.
Originally the group was to be called The Hookers, and would feature Prince's personal assistant at the time, Jamie Shoop, Susan Moonsie (whom Prince was dating in 1981). Moosie's sister Loreen was considered as well and at the time they took few Polaroid photo's with this line-up, with all three girls wearing lingerie and Jamie Shoop chain smoking.
Then shelved the project to fully commit to his forthcoming Controversy Tour in November 1981.
Whilst on tour Prince met Denise Matthews, a young Canadian model and aspiring actress. It is often reported they met at the American Music Awards in January 1982, but according to photographer Allen Beaulieu who was traveling on the tour she harassed the crew for backstage passes on various tour stops and eventually Beaulieu introduced her to Prince, who then proposed her to be part of the project. After Denise Matthews refused Prince's idea to rename her Vagina, the name of Vanity came up, and the band name changed accordingly.
A third band member for the project was also found during the Controversy Tour. Brenda Bennett, his set and lighting designer Roy Bennett's wife was on the tour accompanying her husband and doing hair and make-up for Prince and the band. She had been part of the Tombstone Blues band in the early-mid seventies. Apart from Brenda, none of the girls had any singing experience when they started recording vocals for their album.