Между тем у диктатуры все еще не было своей тайной полиции. В первые месяцы режима существовавшие до этого департаменты полиции избавились от известных политических оппонентов; многие добровольно занимались преследованием левых радикалов задолго до прихода к власти Гитлера, и они не нуждались в особом поощрении, чтобы воспользоваться более широкими полномочиями, которые им предоставляли чрезвычайные законы. Один из таких деятелей, молодой прусский детектив по имени Рудольф Дильс, предложил Герингу преобразовать Прусское управление в новую тайную полицию. 26 апреля 1933 года Тайная государственная полицейская служба [Geheime Staatpolizeiamt] была формально основана с Дильсом в качестве ее первого директора. Акроним ГПА посчитали слишком схожим с советским ГПУ. Один неадекватный чиновник предложил аббревиатуру «гестапо»; таким образом, полицейские силы стали известны как гестапо, тайная государственная полиция. 20 апреля 1934 года организация была передана в компетенцию Генриха Гиммлера, поднявшегося за год от главы отдела полиции в Баварии до руководителя полицейских сил всей Германии. Головной офис гестапо был расположен в Берлине на улице Принц Альбрехтштрассе, 8, а ее руководителем назначили брутального и честолюбивого полицейского из Баварии Генриха Мюллера. Это здание, как и здание на Лубянке в Москве, стало квинтэссенцией всей системы политических репрессий, узаконенных в 1933 году.
В первые годы режима традиционная полиция и суды продолжали играть свою роль в политических репрессиях, используя юридические инструменты, уже имевшиеся в уголовном кодексе, и борясь с преступлениями против общественного порядка и актов предательства. К началу 1935 года в стационарной государственной тюремной системе содержались 22 000 политических заключенных35. Разница между подразделениями политической полиции и остальным полицейским аппаратом состояла в том, что первые имели право задерживать и содержать подозреваемых в предварительном заключении. Это право было дано политической полиции в первый раз в качестве чрезвычайных полномочий после пожара в Рейхстаге. Оно приобрело центральное значение для практики репрессий, но требовало более тщательной формулировки, и его необходимо было периодически возобновлять. К началу июля 1933 года, по данным Министерства внутренних дел, в предварительном заключении находилось 26 789 человек; фактически же это означало, что людей содержали в концентрационных лагерях без права на рассмотрение их дел в суде. Со стороны общественности и чиновников постоянно звучали жалобы на явные злоупотребления, которые влечет за собой такая система. В 1933 году большая часть временных лагерей была закрыта. В апреле 1934 года министр Вильгельм Фрик, нацистский юрист, которому полиция все еще продолжала подчиняться, по крайней мере в теории, опубликовал четкое руководство по «предупредительным заключениям». И хотя теперь несчастные заключенные имели право быть информированными письменно в течение 24 часов о причинах их задержания, никаких ограничений не было предусмотрено в отношении их ареста, поскольку они продолжали, по мнению властей, представлять собой «угрозу общественной безопасности и порядку»36.