Pod koniec lat 50. XX w. byli więźniowie Pawiaka rozpoczęli starania o uczczenie miejsca pamięci męczeństwa i śmierci tysięcy Polaków z okresu zaborów i niemieckiej okupacji niemieckiej oraz ocalenie zachowanych śladów po dawnym Pawiaku. W lutym 1959 r. w „Życiu Warszawy” ukazał się artykuł Poli Gojawiczyńskiej pt. A Pawiak?, w którym znana pisarka zaapelowała o upamiętnienie tych, którzy tu cierpieli i zginęli. Było to bowiem miejsce nie tylko nieopisanych cierpień, zwątpień i śmierci, ale i oporu, hartu, wzrostu człowieka. Apel Gojawiczyńskiej szybko podchwycili byli więźniowie, kombatanci i społeczeństwo. Jeszcze w tym samym roku rozpoczęto prace porządkowe na terenie byłego więzienia, który został wydzielony z ogólnego planu zabudowy dzielnicy muranowskiej. Podjęto też decyzję o powstaniu muzeum, zachowaniu ocalałych fragmentów murów oraz rozpisaniu konkursu na budowę pomnika, który stanąłby na terenie byłego więzienia.
W Muzeum zachowała się Księga Pamiątkowa z 1959 r. z wpisami osób odgruzowujących teren Pawiaka. Pierwszy wpis pochodzi z sierpnia 1959 r. od byłych więźniów Pawiaka, którzy włączają się w prace związane z porządkowaniem Pawiaka. Są wśród nich: Pola Gojawiczyńska, Stanisław Tomaszewski „Miedza”, Maria Tomicka, Krystyna Ciesielska-Brzezowska, Stanisław Zelent. W Księdze figuruje też m.in. wpis nauczyciela i uczniów ze Szkoły Podstawowej nr 210 im. Bohaterów Pawiaka z dn. 15 września 1959 r.: Pracowało 35 dzieci: przerzuciły cegłę i gruz. Wszyscy pracowali bardzo dobrze.
Początkowo prace przy odgruzowywaniu Pawiaka prowadzono w czynie społecznym. W połowie 1960 r. decyzją Stołecznej Rady Narodowej prace nad odgruzowywaniem terenu powierzono Zarządowi Dróg i Mostów Prezydium Rady Narodowej m.st. Warszawy. Do stycznia 1962 r. zabezpieczono wszelkie pozostałości dawnego Pawiaka, m.in. fragmenty wyposażenia: kraty, kotły, futryny okienne, łóżka więzienne i łóżeczko dziecięce z „Serbii” oraz jedyne zachowane drzwi do celi; przedmioty osobiste więźniów oraz ocalone dokumenty. Relikty zostały złożone w Muzeum Historii Polskiego Ruchu Rewolucyjnego w Warszawie, którego oddziałem miało być powstające muzeum.
15 stycznia 1963 r. został powołany Klub byłych Więźniów Politycznych Pawiaka. 21 czerwca 1963 r. na kolejnym zebraniu Klubu powołano Radę Upamiętnienia Pawiaka, która opracowała założenia przyszłego Muzeum, a w zasadzie zespołu pomnikowego. Miał on zajmować ok. 8000 m2, w skład którego wejdą: zachowany fragment bramy wjazdowej oraz drzewo od strony ul. Dzielnej, pomieszczenia dwóch oddziałów więziennych w budynku w formie kurhanu, plac spacerowy, pomnik (autorstwa Z. Pociłowskiej – J.G.) i płyta pamiątkowa o kobiecym oddziale, tzw. „Serbii”. W budynku – kurhanie, o długości 80 m, zrekonstruowany ma być korytarz, w którym rewidowano przyprowadzonych więźniów oraz 4 cele VII oddziału i częściowo – oddział VIII. Powyższe założenia zostały zrealizowane.
