Extraordinary is the tenth and final track on Prince's 22nd album The Vault... Old Friends 4 Sale. Two weeks prior to the album's release, Extraordinary was released as a promo-only single in the USA, but no commercial release was planned. Soon afterwards, it was included as the second and final track on a Japanese promo-only single of The Rest Of My Life. In 2002, a live version of the track was included as the fourth track on the first disc of Prince's first live album One Nite Alone... Live! (along with Xenophobia, Avalanche, Family Name, Raspberry Beret, The Everlasting Now, Wanna B Ur Lover, Diamonds & Pearls, The Beautiful Ones, Nothing Compares 2 U and How Come U Don't Call Me Anymore from the same show).
While specific recording dates are unknown, basic tracks were recorded in September 1992 at Paisley Park Studios in Chanhassen, Minnesota (during the same set of sessions that produced Down, Holly Don't Care, The P, The Halls Of Desire, Paris 1798430, Uncle Sam, Super Hero and a remake of Shhh). The song was originally intended for Rosie Gaines' planned solo album Concrete Jungle, and she recorded vocals for the track, although Prince reclaimed the track before the known configurations of Concrete Jungle were compiled in 1993.