Katrina's Paper Dolls was released posthumously in 2017, as the ninth track on the second disc (titled From The Vault & Previously Unreleased) of Purple Rain Deluxe.
The track was recorded on a day off on the 1999 Tour at Universal Recording Corporation, Chicago, Illinois, presumably on 1 March 1983 between shows in Pittsburgh, Pennsylvania and Peoria, Illinois. It is unlikely that the song was initially intended for Purple Rain.
In an online Q&A in 2009, Lisa Coleman stated that she co-wrote the track with her sister Cole Ynda Coleman and Wendy Melvoin during the same few-day session as Power Fantastic (recorded 19 March 1986), but given that the track had been written and recorded by Prince three years earlier, it's unclear what she meant by that. It's possible the track was re-recorded with newly-written music, and is noted as such below, but this is unconfirmed.
During Prince: A Celebration in June 2000, computer screens at Paisley Park Studios in Chanhassen, Minnesota, offered names of a selection of tracks which users could vote on for inclusion on Crystal Ball Volume II, and while Katrina's Paper Dolls was chosen by fans, the project was ultimately abandoned.
While a solo recording, it is listed here as a Prince and the Revolution track as it was released as a bonus track on the Purple Rain Deluxe album, which is credited to Prince and the Revolution.
The Katrina name is possibly in reference to Vanity whose full name was Denise Katrina Matthews.