Nagrania do albumu odbywały się w studiu w Nowym Jorku. Pierwsza nagrana wersja „Lucky Star” była w stylu R&B. W innej zostały dodane gitary, jednak ze względu na negatywne wspomnienia Madonny z bycia rockową gitarzystką wersja ta nie została nigdy dokończona. W trakcie nagrań do albumu narastały napięcia w związku z faktem, że według artystki brzmienie zaczynało za bardzo odbiegać od oryginalnych wersji demo. zrezygnował z dalszej współpracy, a Madonna zwróciła się z prośbą o zremiksowanie trzech piosenek do swojego ówczesnego partnera, . Do „Lucky Star” dodał gitarowe riffy, syntezatorowy beat w stylach disco, soul i nowej fali, a także dodatkowe wokale.
Analiza utworu thumb|left|upright|Madonna wykonująca „Lucky Star” podczas koncertu w Londynie w ramach trasy Who’s That Girl World Tour (1987) „Lucky Star” jest dance-popowym utworem w średnim tempie, z elementami disco i nowej fali oraz brzmieniem opartym na syntezatorach. Redaktorzy „Rolling Stone” określili jego syntezatorowe intro jako „migoczące”. Eric Henderson, dziennikarz portalu Slant Magazine, napisał, że piosenka rozpoczyna się od „migoczących, zaprogramowanych glissando”, które następnie przechodzą w „brzęczące gitary rytmiczne, atmosferyczne dźwięki syntezatora i dudniącą linię basu”.