Pierwotnie wytwórnia planowała wydać „Lucky Star” jako trzeci oficjalny promujący go singel, ale ostatecznie wybór padł na „Holiday” z uwagi na jego popularność w radiu.
9 września 1983 roku „Lucky Star” został wydany jako czwarty samodzielny singel promujący album, początkowo tylko w Europie. Na jego stronie B znalazła się piosenka „I Know It”. W Stanach Zjednoczocych ukazał się 8 sierpnia 1984 roku, jako piąty i ostatni singel promujący album. 27 lipca 2023 roku został wydany w dystrybucji cyfrowej.
Utwór znalazł się na kompilacjach największych przebojów Madonny: The Immaculate Collection (1990) i Celebration (2009).
Odbiór krytyków Po premierze singla dziennikarz magazynu „NME” pochwalił go jako lepszy niż wcześniej wydany „Everybody”, przypisując to produkcji . Recenzent magazynu „” pochwalił Madonnę za „charakterystyczny wokal i talent liryczny”. W recenzjach albumu Madonna Brian Chin z czasopisma „Billboard” nazwał go najlepszym utworem, zaś Roger Le Lievre z gazety „” określił jako „klejnot o bujnym brzmieniu”.