Однако укрепление личной власти Гиммлера в этой германской земле произошло не сразу. Поначалу рейхсфюрер СС предпочитал действовать через своего знакомого Вальтера Шталекера, который в мае 1933 года был назначен заместителем начальника политической полиции. Однако в ноябре 1933 года на этом посту его сменил тяготевший к руководству СА Герман Маттхайс. Несмотря на это, Гиммлеру удалось добиться того, что 9 декабря 1933 года он все-таки был назначен начальником политической полиции Вюртемберга. В данном случае свою роль могли сыграть два обстоятельства. Во-первых, желание имперского наместника Мурра сделать аппарат политической полиции «более эффективным». Во-вторых, нельзя сбрасывать со счетов тот факт, что осенью 1933 года руководство СД в Штутгарте (оберабшнитт «Юго-Запад») было поручено весьма энергичному Вернеру Бесту. Однако окончательно свою власть в Вюртемберге Генрих Гиммлер смог укрепить только к маю 1934 года, когда от должности был отстранен Герман Маттхайс. Он был убит некоторое время спустя во время «ночи длинных ножей». Шталекер же сделал карьеру в полиции порядка, а Мурр 9 сентября 1934 года обрел чин группенфюрера СС.
18 декабря 1933 года Гиммлер принял командование политической полицией Бадена. Здесь в дело должен был вмешаться Гитлер. Именно от его имени Рудольф Гесс «ходатайствовал» о назначении Генриха Гиммлера. Показательно, что «ходатайство фюрера» рассматривали местный гауляйтер Роберт Вагнер и баденский министр внутренних дел Пфлаумер, которые к этому времени уже были служащими СС.
В Бремене Гиммлеру пришлось столкнуться с некоторыми трудностями. Первые личные контакты с местными партийными руководителями Гиммлер установил в мае 1933 года. Однако в октябре 1933 года Гиммлер оказался втянутым в конфликт, который возник между начальником полиции Теодором Лауэ и местными штурмовиками. Дело дошло до того, что Эрнст Рём был вынужден исключить Лауэ из рядов СА. И это при том условии, что Лауэ считался одним из создателей штурмовых отрядов. После этого Лауэ волей-неволей был вынужден искать поддержки у Гиммлера. На тот момент рейхсфюрер СС уже имел верного союзника в лице шефа бременской тайной государственной полиции Эрвина Шульца. Шульц уже давно был осведомителем СС, а до этого — тайной государственной полиции Бремена. После того как была подготовлена почва для переговоров, Гиммлер встретился с имперским наместником Карлом Ровером и бургомистром Рихардом Маркертом. 22 декабря 1933 года Гиммлер стал главой тайной полиции Бремена. 5 января 1934 года аналогичное известие пришло из Ольденбурга. Кроме этого Гиммлеру зимой 1933/34 года фактически без проблем удалось подчинить себе политическую полицию Гессена, Тюрингии и Саксонии. В Бауншвейге, Липе и Шаумбурге Гиммлеру пришлось приложить определенные усилия. После некоторого сопротивления со стороны местных партийных функционеров он все-таки смог добиться желаемого.