We wrześniu 1999 nagrano alternatywną wersję piosenki, ponieważ Aguilera obawiała się, że wersja albumowa nie posiada singlowego potencjału. Zwiększono tempo singla, zmieniono „przejście”, dodano „break” oraz partie wokalne i tekstowe. Wersja alternatywna utworu jest krótsza od oryginalnej o trzydzieści sekund. Hiszpańskojęzyczna edycja „What a Girl Wants”, zatytułowana „Una mujer”, znalazła się na albumie Mi Reflejo Aguilery z 2000 roku.
Wydanie singla „(...) Chciałam, by po 'Genie in a Bottle’ następnym singlem promującym moją debiutancka płytę został 'What a Girl Wants’. Firma namawiała mnie do czegoś innego. Nie dałam się przekonać, choć naciskali. Okazało się, że miałam rację. Utwór stał się przebojem i dotarł na pierwsze miejsce Billboardu.” – Aguilera wypowiada się na temat singla i wspomina o sukcesie, jaki osiągnął„XTINA.PL || WYWIADY || PLAYBOY (2000)”. xtina.pl. [dostęp 2013-09-14]..
Światowa premiera singla przypadła na zimę 1999, 28 grudnia tego roku;