Powstawanie Lisa Stevens i Curtis Hudson napisali „Holiday” dla zespołu , w którym występowali. Stevens skomponowała go na keyboardzie jako balladę. Następnie Curtis dodał linię basu i wymyślił hook „holiday, celebrate”. W kolejnych dniach stworzył większość tekstu, do którego Stevens dopisała fragmenty, a także przygotował aranżację. Inspirację stanowił dla niego pomysł, że dobrą rzeczą dla świata w depresyjnych czasach byłyby jednodniowe wakacje. Zespół Pure Energy nagrał utwór w stylu soulowym i gospel, z użyciem pianina Rhodes, perkusji i instrumentów smyczkowych. Ich wytwórnia, Prism Records, nie chciała go wydać, więc Stevens i Hudson usiłowali sprzedać go komuś innemu. Ostatecznie zaoferowali ją swojemu znajomemu , który poszukiwał ostatniego utworu na album Madonny.
Nagranie piosenki odbyło się w studiu w Nowym Jorku z budżetem w wysokości 5 tysięcy dolarów. Było pierwszą oryginalną produkcją muzyczną, jaką Benitez wykonał w życiu. Stevens i Hudson byli obecni podczas sesji. Hudson zagrał na gitarze, jego brat Raymond na gitarze basowej, zaś jego znajomy Bashiri Johnson na perkusji. zagrał na syntezatorach i , sekwencerze i klawiszach. Pod koniec piosenki dodał overdubbingową partię solową na klawiszach.