"Я чувствую, что должен теперь что-то предпринять, чтобы спасти Германию, - сказал он своей жене, графине Нине, матери четырех маленьких детей, когда она приехала в госпиталь навестить его. - Мы, офицеры генерального штаба, обязаны взять на себя свою долю ответственности".
К концу сентября 1943 года он вернулся в Берлин в чине подполковника и получил назначение на должность начальника штаба у генерала Ольбрихта в управлении сухопутных войск. А вскоре он, используя три пальца здоровой руки, начал учиться обращению с имевшимися в абвере бомбами английского производства. Но этим он не ограничился. Ясность мышления, религиозность, незаурядный организаторский талант вселили решимость в заговорщиков, однако породили и определенные разногласия, поскольку Штауфенберга не удовлетворял тот громоздкий, консервативный, бесцветный режим, который намеревались установить в Германии после падения национал-социализма престарелые, с заскорузлым умом руководители заговора Бек, Герделер и Хассель.
Отличаясь большей практичностью, чем его друзья из кружка Крейсау, Штауфенберг ратовал за учреждение новой, динамичной социал-демократии и настаивал на том, чтобы в намечаемый состав антинацистского кабинета были включены его новый друг Юлиус Лебер, блестящий социалист, и бывший профсоюзный лидер Вильгельм Лойшнер - активные и деятельные участники заговора. Возникли серьезные разногласия, но Штауфенберг быстро доказал свое превосходство над политическим руководством готовящегося переворота.
В равной мере он добился успеха в отношениях с большинством военных лиц. Он признал генерала Бека их номинальным лидером и с восхищением относился к бывшему начальнику генерального штаба. Однако по возвращении в Берлин он увидел, что Бек после сложной онкологической операции превратился в подобие прежнего Бека: усталый, утративший боевой дух, не выработавший определенной политической концепции, он всецело полагался на Герделера. Прославленное в военных кругах имя Бека могло бы сослужить пользу при осуществлении путча, но для активного вовлечения в него войск и управления ими следовало мобилизовать молодых офицеров, находившихся в действующей армии. Вскоре Штауфенберг собрал вокруг себя большинство ключевых фигур, из числа тех, кто был ему нужен.
Помимо Ольбрихта, его начальника, это были: генерал Штифф, глава организационного управления сухопутных войск (ОКХ); генерал Эдуард Вагнер, первый генерал-квартирмейстер сухопутных войск; генерал Эрих Фельгибель, начальник службы связи при верховном главном командовании (ОКВ); генерал Фриц Линдеман, начальник артиллерийско-технического управления; генерал Пауль фон Хазе, начальник берлинской комендатуры (он мог выделить войска для захвата Берлина); полковник барон фон Ренне, начальник отдела иностранных армий, и его начальник штаба капитан граф фон Матюшка.
К числу заговорщиков примыкали еще два или три занимавших ключевые должности генерала, чьим начальником был Фриц Фромм, фактический командующий армией резерва, который, подобно Клюге, постоянно менял свои взгляды и на которого нельзя было полагаться всерьез.
В рядах заговорщиков не было ни одного фельдмаршала из состоявших на действительной службе. Фельдмаршала фон Вицлебена, который одним из первых примкнул к заговору, намечали на должность главнокомандующего вооруженными силами, но пока он числился в резерве и не имел в своем подчинении войск. Прозондировали и фельдмаршала фон Рундштедта, который в то время командовал всеми войсками на Западе, однако он не пожелал нарушить присягу, данную фюреру, - так, по крайней мере, объяснил он свою позицию. Впрочем, как и блестящий, но склонный к авантюризму фельдмаршал фон Манштейн.
В начале 1944 года, еще не зная о существовании Штауфенберга, один очень активный и популярный фельдмаршал проявил что-то вроде готовности примкнуть к заговорщикам. Это был Роммель, Его вступление в заговор против Гитлера явилось большой неожиданностью для руководителей Сопротивления и не встретило одобрения со стороны большинства из них. Они считали Лису Пустыни нацистом, приспособленцем, явно добивавшимся расположения Гитлера, а теперь покидавшим его, поскольку стало ясно, что война проиграна.