Na potpunu slobodu pušten je [[mart]]a 1956 godine, posle punih dvadeset godina zatočeništva. Nešto pre toga Vrhovni kolegijum Vrhovnog suda SSSR-a doneo je odluku o njegovoj rehabilitaciji. Posle napuštanja Maklakova, došao je u Moskvu, kod žene. Ubrzo potom je odlučio da se vratu u FNR Jugoslaviju, koju je nazivao svojom domovinom. Uz pomoć tadašnjeg jugoslovenskog ambasadora [[Veljko MilatovićMićunović|Veljka MilatovićaMićunovića]], dobio je izlaznu dozvolu i [[30. 7.]] 1956 napustio je SSSR. Po povratku u FNR Jugoslaviju, nastanio se u Zagrebu. Bavio se publicističkim radom, i pri tome je objavio tri knjige.<ref name="kš"/> Njegova prva knjiga "7000 dana u Sibiru", u kojoj je opisao svoje nedaće tokom 20-o godišnje robije, bila je veoma popularna u [[Socijalistička Federativna Republika Jugoslavija|SFR Jugoslaviji]], doživela je 24 izdanja i prevođena je na nekoliko stranih jezika. Godine [[1972]] je od strane lista [[Vjesnik]] proglašena za knjigu godine, a on je kao autor dobio Nagradu [[Ivan Goran Kovačić]], za najbolju knjigu godine.<ref name="kš"/> Prema vlastitoj autoidentifikaciji, Karlo Štajner je do kraja života ostao jugoslavenski komunist.<ref name="mj">{{Citiranje www|naslov=Mrtve oči Sonje Štajner|url=http://www.jergovic.com/subotnja-matineja/mrtve-oci-sonje-stajner/|autor=Miljenko Jergović|autorlink=|prezime=|ime=|koautori=|urednik=|izdavač=jergovic.com|format=|rad=|stranice=|dan=|mjesec=|godina=31. 5. 2014|preuzeto=5. 10. 2015|arhivurl=|arhivdatum=|citat=}}</ref>
