Stewart Mason, redaktor portalu AllMusic, określił ją jako minimalistyczną, a jej aranżację jako surową, ponadto zwrócił uwagę na funkowy łącznik. Stephen Thomas Erlewine z serwisu The A.V. Club napisał: „To brzmienie stworzone z myślą o parkietach tanecznych, ale ostatecznie przyćmiewa je melodia Madonny, napędzana żarzącym, popowym hookiem”. Es Masley, dziennikarz czasopisma „”, porównał brzmienie do późnej twórczości zespołu Chic, zaś Roger Le Lievre z gazety „” do . Henderson ocenił, że śpiew Madonny brzmi jak zabarwiony helem.
Tekst jest zaadresowany do człowieka nazywanego „szczęśliwą gwiazdą”. Według redaktorów „Rolling Stone’a”, słowa utworu opierają się na dwuznacznym znaczeniu jego „niebiańskiego ciała”. Masley zinterpretował to określenie jako aluzję seksualną. W tekście pojawia się klasyczna dziecięca rymowanka „” („światło gwiazd, jasnych gwiazd”).
Wydanie Latem 1983 roku wytwórnia Sire Records wysłała do klubów nocnych promocyjny singel z podwójną stroną A, zawierający utwory „Holiday” i „Lucky Star”. Premiera albumu Madonna, na którym znalazły się piosenki, odbyła się 27 lipca 1983 roku.