Штауффенберг прекрасно справился с планированием военной операции. Но куда сложнее было справиться с соперничеством планов, а также честолюбием и с задними мыслями. С некоторой наивностью, замешанной на хорошей порции реакционного цезаризма, он верил в идеальный порядок, при котором мессия мог бы собрать вокруг себя своих апостолов ради спасения Германии. Мир политики был ему совершенно чужд, часто по причине полного расхождения с его манерой мышления и существования. Попадание в котел конкретных действий стало для него суровым испытанием, где он, однако, доказал свою зрелость.

Перед своим отъездом в Тунис он при посредничестве Бертольда встретился с большинством из «ветеранов» группы Герделера — Бека и с «реформаторами» кружка «Крейзау». 8 января 1943 года он даже принял участие в собрании под председательством Бека. По возвращении с фронта он возобновил установленные ранее контакты. Но все, так или иначе, его раздражало.

Ему были достаточно близки идеи Горделера. Но его политические приемы, разговоры терминологией партий, министерств, площадей, его неосторожность и оторванный от реальности оптимизм, равно как и его претензии на пост канцлера после государственного переворота, казались Клаусу совершенно неуместными. В условиях, когда популярность фюрера в народе еще высока, вызов должен был, как он считал, прозвучать убедительно. Требовалось либо найти харизматичного лидера, каковым Герделер не являлся, либо поставить канцлером всех устраивавшего человека, который смог бы показать, что кузнецы новой Германии вовсе не были кадилоносцами старого порядка, а были инициаторами продуманного обновления страны. Штауффенберг предложил на этот пост кандидатуру Вильгельма Лейшнера, профсоюзного деятеля и бывшего депутата от СПГ, с которым он встречался благодаря кружку «Крейзау». Как же возмутились Герделер и Хассель! Они считали, что это означало бы протаскивание через окно большевизма, который был выставлен за дверь при Веймарской республике. Штауффенберг не был в этом уверен, но ничего не сказал. И все-таки сумел добиться, чтобы его протеже был рассмотрен на пост вице-канцлера. Решение Герделера назначить политических руководителей к офицерам по связи в каждом военном округе также казалось ему скандальным. Если даже такие личности, как Хайнрих фон Дона в Кенигсберге или Эвальд фон Клейст-Шменцин в Штеттине, были вне всяких подозрений, то назначение к ним политических руководителей означало бы возрастание опасности утечки информации вдвое.

Еще больше его беспокоил Попиц. Он полагал, что, когда человек считает себя слишком ловким, талантливый кукловод в конечном счете сам может запутаться в своих нитках. Он был просто взбешен, узнав о том, что бессменный министр финансов имел контакты с Гиммлером. И резко выступил против этого, пригрозив выйти из состава группы, если эти контакты будут продолжены. Арест гестапо адвоката из «конюшни» Попица Карла Лангбена подтвердил его подозрения. Мы не знаем точно, что потом предпринял этот политический интриган, но точно известно, что волк положил глаз на эту овчарню.

С членами кружка «Крейзау» он испытывал трудности другого порядка. Высокие этические нормы этих людей воспрещали им идти на компромиссы. Это делало их слепыми, когда требовалось действовать. Больше всего его злил Мольтке. Похожий с виду на худого пастора, тот постоянно старался прочесть мораль и требовал уважения к категорическому императиву. В ходе одной встречи на Гортензиен-штрассе у Йорка фон Вартенбурга, в то время, когда люди погибали в лагерях, горели в огне, он раскритиковал предложение Штауффенберга о покушении. «Действуй так, чтобы твой поступок мог быть при этом общим правилом», — сказал он ему. Клаус ушел, хлопнув дверью, произнеся при этом слова Гегеля: «Вы хотите иметь чистые руки, но у вас нет рук». Подобные стычки происходили все чаще. В ноябре 1943 года он разгорячился и сказал: «Времена чаевничания и салонных разговоров прошли». А затем ушел с собрания вместе с Аннабель Сименс, которой заявил: «Идем домой. Этот Мольтке не в состоянии вынести вида даже капли крови». Арест Мольтке в январе 1944 года снял многие трудности, тем более что остальные члены кружка были ему очень симпатичны, особенно Йорк фон Вартенбург, оказавший ему помощь в налаживании контактов с левыми.

В ноябре 1943 года Клаус познакомился, таким образом, с Юлиусом Лебером. Они были совершенно разными людьми. Известный журналист, Лебер по происхождению был пролетарием, по убеждению — марксистом. Некоторое время он проработал главным редактором газеты «Любекер фольксберихт», а во времена Веймарской республики был депутатом от СПГ. Объединяло их то, что оба были офицерами. В звании лейтенанта Лебер отличился в войне 1914 года. Был награжден, трижды отмечен в приказе. Он был одним из немногих в социалистической партии, кто защищал интересы армии. Этого было вполне достаточно, чтобы завоевать доверие Штауффенберга. Тем более что теперь бывший марксист больше верил в людей, нежели в идеи. Он был готов участвовать в возрождении открытой и плюралистической Германии. Очень скоро между ними установились подлинные дружеские отношения. Лебер даже попытался убедить своего друга войти в контакт с действовавшей в подполье коммунистической партией, КПГ. Но Клаус и Лейшнер от этого воздержались. Они не хотели, чтобы вместо коричневой чумы страну поразил красный рак. Но, несмотря на все, Лебера попросили тайно встретиться с представителями КПГ Антоном Зевтковым и Францем Якобом. Первая такая встреча состоялась 22 июня 1944 года. Лебер вел себя осторожно и лишь намеками поведал о возможном государственном перевороте. Коммунисты скрепя сердце согласились дать гарантии свободы вероисповедания и права собственности. Но потребовали, чтобы Красная армия заняла часть Германии. Следующая встреча была назначена на 4 июля. Но в тот день все пошло вовсе не так, как было намечено. Вместо двух членов КПГ пришли трое. Третьим был внедренный в их партию агент гестапо. На другой день Лебер был арестован. Под пытками он никого не выдал. Но заговорщиков охватила тревога, и все стали винить Штауффенберга. Некоторые обвинили его в том, что он совершил проступок по своей наивности. Невозможно было предположить, что этот арест был случайным. Считалось, что коммунисты предпочли торпедировать план переворота, разоблачив заговор, который якобы мог лишить Москву важного козыря в Европе.

Но Клаусу все-таки удалось подобрать работоспособное правительство, представлявшее весь спектр политической жизни Германии. Задача была не из легких. Все знали об ожесточенности боев на фронтах, об угрозе ареста и хрупкости заговора. И ему казалось поразительным, что делили шкуру еще не убитого медведя. После многочисленных обсуждений и споров 26 мая 1944 года в ходе встречи Герделера, Хасселя и Йорка были наконец определены основные члены будущего кабинета министров. Потом были некоторые перестановки, но баланс сил сохранялся. Бек должен был стать главой государства, Герделер — канцлером, Лейшнер — вице-канцлером. Пост главы Министерства иностранных дел теоретически отходил к Хасселю, даже несмотря на то, что бывший посол в Москве Фридрих фон Шуленбург делал все, чтобы получить этот портфель. При этом он упирал на то, что его знание России могло облегчить переговоры с противником, стоявшим у границ рейха. Министром внутренних дел должен был стать Лебер, а Министерство юстиции отдавалось Йозефу Виремейру, бывшему представителю центра. Министром финансов должен был стать Попиц или Эвальд Лезер. Генерал Хепнер — министром обороны.

Петер Йорк фон Вартенбург становился государственным секретарем рейхсканцелярии с задачей координации деятельности этой разношерстной коалиции. Огромным успехом Штауффенберга стало то, что он сумел заставить работать вместе стольких честолюбивых людей. В этом полностью проявились его умение вести переговоры и его сила убеждения. Ему пришлось побороться за то, чтобы сделать невозможное: свести вместе бывших членов НННП и представителей СПГ. Работа по формированию этого фантомного правительства преобразила Клауса. Вместо экзальтированного молодого человека, противника новых сил, предстал умелый человек действия, готовый к компромиссам, способный глядеть в будущее и с широким кругозором. Реальность возобладала в нем над его убеждениями. В 1944 году он проявил себя настоящим государственным деятелем. Он преодолел узость своих убеждений и поднялся над своими природными наклонностями.