Pomysł wzniesienia Pałacu Kultury i Nauki jako „daru narodu radzieckiego dla narodu polskiego” wyszedł od samego Józefa Stalina, który oprócz PKiN zaproponował Bolesławowi Bierutowi do wyboru budowę metra lub osiedla mieszkaniowego w Warszawie. Bierut wybrał pałac, uznając (wedle przekazu Włodzimierza T. Kowalskiego w książce „Walka dyplomatyczna w Europie: 1939–1945”), że metro jest niepotrzebne, a osiedle Polacy wybudują sobie sami.
Rozważano wzniesienie pałacu w okolicach Portu Praskiego, na Grochowie lub na Mokotowie. Ostatecznie padło na centrum miasta, jako najbardziej reprezentacyjne. Były to kwartały między ulicami Chmielną, Złotą, Sienną, Śliską, Pańską, Zielną i Wielką. Na tym powojennym gruzowisku ocalało kilkadziesiąt kamienic nadających się do użytku bądź remontu, które trzeba było wyburzyć (pod samą budowlę, jak i obszerny plac Defilad).
Zespołowi architektów sowieckich przewodził Lew Rudniew, a współpracowała z nimi grupa architektów polskich z Józefem Sigalinem na czele. Cała grupa wybrała się w podróż po Polsce, by obejrzeć najważniejsze zabytki, a potem wprowadzić do projektu polskie akcenty. Budowa ruszyła 2 maja 1952 r. Pracowało przy niej 3,5 tys. robotników z ZSRR, dla których wybudowano na Jelonkach osiedle Przyjaźni Polsko-Radzieckiej, złożone z baraków i tzw. domków fińskich – dla inżynierów.
PKiN oddano uroczyście do użytku 22 lipca 1955 r. i nazwano imieniem Józefa Stalina, o czym przez długie lata świadczył napis wykuty nad głównym wejściem od strony ul. Marszałkowskiej, przysłonięty potem przez neon bez nazwiska patrona.