What's My Name is the fourth track on the second disc of Prince's 20th album Crystal Ball (his fourth using the name ). The album is not clearly divided between Prince tracks and tracks, but, despite the track's title, the timing of the track's recording places it shortly before his public announcement of his name change to , and the liner notes' discussion of this track state "After the increasing amounts of lollipops using the name Prince, the original came hard with this one", so it is credited to Prince in this entry. A portion of the song was premiered on 14 June 1993 on the "Paisley Park Hotline" telephone service, which promised to reveal Prince's new name (having announced the name change to on 7 June 1993). Instead, the song only created more confusion about his name. In August 1993, What's My Name was included in the Glam Slam Ulysses stage-show, during the segment titled "Scylla" (segueing directly into the uncredited track Poem, later reworked as Orgasm).
In 2011, a significant portion of the song was included, uncredited, in a live version of Flash Light, which was streamed as a YouTube video (audio only, with a static image) on bandmember Andy Allo's Facebook page within hours of its performance (What's My Name had been performed in full for the first time ever earlier in the show).
While specific recording dates are not known, basic tracking took place in mid to late May 1993 at Paisley Park Studios in Chanhassen, Minnesota (during the same set of sessions that also produced Space, Pope, Strays Of The World, Interactive, Solo, and a reworked version of Race).