Budynek Mauzoleum – według projektu inż. arch. Mieczysława Mołdawy pod kierunkiem generalnego projektanta prof. Romualda Gutta – został wybudowany na ocalałych fundamentach i zachowanych fragmentach piwnic oddziałów VII i VIII dawnego więzienia. Wejście do przyziemi zaplanowano na miejscu dawnego wejścia głównego do Pawiaka. Zachowano ocalałe fragmenty ścian dawnego więzienia, których wysokość w zrekonstruowanych celach dochodzi do 1,5 m. Podczas budowy wykorzystano też większość znalezionych w czasie odgruzowywania obiektu krat, zawiasów, sztab, zamków i okuć. Na zrekonstruowanym dziedzińcu oznaczono za pomocą marmurowych płyt punkty szczególne: zejście do kostnicy więziennej, miejsce wagi węglowej, na słupie której 6 grudnia 1943 r. publicznie powieszono trzech więźniów za próbę ucieczki oraz miejsce, gdzie na hałdzie gorącego żużlu i popiołu z pieców centralnego ogrzewania oprawcy kazali czołgać się więźniom. W ostatnich latach powrócono do pierwotnej koncepcji „wypełnienia” dziedzińca płytami upamiętniającymi poszczególne obozy i organizacje. Obecnie znajdują się na „zewnętrznym” dziedzińcu od strony ulicy Dzielnej.
Prace przy budowie Muzeum Więzienia Pawiak zostały sfinansowane przez Społeczny Fundusz Odbudowy Stolicy. Zanim doszło do uroczystego otwarcia Muzeum Więzienia Pawiak, 26 września 1964 r., w lokalu Centralnego Ośrodka Doskonalenia Kadr Kierowniczych przy ul. Wawelskiej 56 otwarto pierwszą wystawę dotyczącą historii Pawiaka w latach 1939–1944, na której zaprezentowano ocalałe z ruin więzienia przedmioty, dokumenty oraz makietę więzienia i projekt przyszłego Muzeum.
Muzeum Więzienia Pawiak otwarto 28 listopada 1965 r. jako oddział Muzeum Historii Polskiego Ruchu Rewolucyjnego. W otwarciu wzięli udział zaproszeni goście, na czele z Marszałkiem Polski Marianem Spychalskim, bardzo licznie przybyli dawni więźniowie, ich rodziny oraz mieszkańcy Warszawy. W imieniu byłych więźniów głos zabrał Zygmunt Śliwicki, lekarz, wieloletni więzień funkcyjny zatrudniony w szpitalu więziennym, który przy akompaniamencie werbli odczytał Apel więźniów Pawiaka, napisany specjalnie na okoliczność otwarcia Muzeum przez płk Zbigniewa Załuskiego.