Став моряком, Гейдрих сохранил связь с ассоциацией, одним из основателей которой был. Получив звание лейтенанта, он был назначен по его просьбе в политический сектор разведывательной службы Балтийского флота. Здесь он приобрел знания, которые очень пригодились ему через несколько лет. Умный и дисциплинированный, он мог бы сделать блестящую карьеру, если бы не тайный изъян, испортивший идеальный ход его судьбы. Гейдрих был сексуальным маньяком, и его случай озадачил бы любого психиатра. Несколько раз любовные истории серьезно угрожали его карьере, пока одна из них, самая серьезная, не положила ей конец. Гейдрих был обручен с дочерью старшего офицера, служившего в арсеналах Гамбурга. Согласно одной версии, он сделал ее своей любовницей, а затем порвал с ней под тем предлогом, что офицер не может жениться на легкомысленной особе; по другой версии, он ее напоил, а затем изнасиловал. Третья версия гласила, что он хитростью выманил у нее деньги. Трудно сказать, какая из них ближе к истине: меры, принятые нацистскими главарями с целью стереть темные пятна в своем прошлом, затрудняют исследование их биографий. Известно только, что инцидент был передан в суд чести. Этот «трибунал» под председательством будущего адмирала Редера счел поведение старшего лейтенанта Гейдриха недостойным и рекомендовал ему подать в отставку во избежание более крупных неприятностей. Таким образом, в 1931 году молодой офицер двадцати семи лет от роду оказался выброшенным на улицу. Как и Гиммлер, Гейдрих пережил тогда довольно трудное время, перебивался с хлеба на воду и вращался среди отбросов общества в северных портах Германии – Гамбурге, Любеке, Киле. Там он свел знакомство с бандитами, которых нацистская партия в борьбе против властей и других партий нанимала для нападения на собрания своих противников и кулачных расправ во время уличных столкновений.
Эти связи, поддерживаемые политическим прошлым Гейдриха, привели его в НСДАП. Партия приобрела в его лице полезного члена. Его образование, военная подготовка и специальные знания делали из него весьма ценного сотрудника. Гейдрих вступил в СС, потому что это было средство для определения его позиции. Вскоре он уже возглавил кильскую группу СС, не очень большую по численности. В этот период его заметил Гиммлер. Он сумел разглядеть исключительные способности своего скрытного подчиненного. 1 августа 1931 года он назначил Гейдриха штурмфюрером, к осени повысил до штурмбаннфюрера (майора) и включил в состав своего штаба в Мюнхене.
В июле 1932 года Гиммлер решил реорганизовать службу безопасности СС и, зная компетентность Гейдриха в данной области, поручил ему эту работу, произведя в штандартенфюреры. После создания СС в каждой воинской части имелись 2–3 человека, занятые обеспечением «безопасности», то есть разведывательной службой. Сам Гиммлер очертил круг обязанностей этих агентов: «В те времена мы, по понятным причинам, располагали разведывательной службой в полках, батальонах и ротах. Было важно знать, что готовят наши противники. Хотят ли, например, коммунисты провести сегодня собрание, произойдет ли внезапное нападение на наших людей, о других событиях такого рода».
В 1931 году Гиммлер отделил работников разведки от остальных подразделений СС и создал закрытую службу безопасности. Новая организация была окрещена им службой безопасности рейхсфюрера СС (СД). Она осталась органом СС, отвечающим за безопасность самого Гиммлера и эсэсовцев вообще.
Возглавив эту новую службу, Гейдрих решил осуществить на практике то, чему его научили в морской разведке. Он построил новую организацию на военный лад, а ее сотрудникам предоставил техническое образование. Он создал разведывательные картотеки, которые существовали на тот момент в неполном виде, однако не смог дать службе должное развитие из-за нехватки кадров. Зато после взятия власти он заполнил ее пробелы, используя собственные методы. Довольный его работой, Гиммлер в 1933 году назначил Гейдриха своим представителем в руководстве баварской полиции, а в 1934 году поставил во главе центральной службы гестапо. Гейдрих не принадлежал к «ветеранам» движения, но имел достаточно солидный партийный стаж, когда утвердился в Берлине, где возглавил гестапо, оставаясь в то же время шефом СД.