Po bitke o Stalingrad požiadal o nové určenie a bol odvelený k 10. obrnenej divízi do Tuniska. 7.4. 1943 nabehlo Stauffenberovo auto na mínu. Prišiel o ľavé oko a mal poranené ľavé ucho a koleno. Stratil pravou ruku a časť prstov na ľavej ruke. Lekári pochybovali, že ťažký úraz prežije. Dlhú dobu sa liečil v nemocnici. Na jeseň 1943 prišiel domov, kde sa zotavil. V lete 1943 oznámil svojim nadriadeným, že sa počas troch mesiacov vráti do služby. V septembri 1943 bol Stauffenberg späť v Berlíne, kde ako podplukovník bol náčelníkom štábu generála Friedricha Olbrichta na vrchnom velitelstve armády. V Berlíne bol skoro kontaktovaný organizátormi prevratu a zakrátko nad nimi získal kontrolu. Trval na tom, že nový režim musí mať protinacistickú vládu a tiež vytvoril zoznam potenciálnych vodcov prevratu. Uvedomil si potrebu mladších dôstojníkov, ktorí by boli schopný získat pre prevrat väčšinu nemeckých dôstojníkov. Na začiatku roku 1944 sa k organizátorom prevratu pridal polní maršál Erwin Rommel, prezívaný "líška púšte". Stauffenberg a rada dalších mu ale nedôverovala. Považovali ho za nacistu, ktorý sa od Hitlera začal odvracať len kvôli neúspechom vo vojne. Rommel byl proti vražde Hitlera pretože se domnieval, že sa z neho tak stane mučeník. Domnieval sa, že Hitler by mal byť súdený za svoje zločiny nemeckým súdom. V tej době by bol dohodnutý separátny mier so Západom a vojna proti Rusom by pokračovala. Stauffenberg a rada jeho kolegov ale vedeli, že Západ nikdy na separátny mier s Nemeckom nepristúpi. Ako sa vojnová situácia zhoršovala, urýchľovali prípravy na odstránenie Hitlera a prevzatie moci. Generál Tresckow začal v lete 1943 pracovať na pláne Operácie Valkýra. Akcia dostala krycí názov podľa prekrásnych panien z nórskej mytológie, ktoré sa vznášali nad bojiskom a rozhodovali o tom, kto zomrie a kto prežije. Operácia Valkýra predstavovala premyslený plán štátneho prevratu, ale tak prezieravo zamaskovaný, že s prípravou niektorých opatrení súhlasil sám Hitler. V zdôvodnení operácie sa uvádzalo, že by bolo potrebné pre prípad vzbury miliónov zahraničných robotníkov zavlečených na nútené práce do Ríše vypracovať preventívne opatrenie k zaisteniu kľudu a poriadku. Rovnako sa upozorňovalo na možné nebezpečie výsadku angloamerických parašutistov s úmyslom provokovať na nemeckom území povstanie. Pre tieto krajné prípady teda vypracovali vzbúrenci strategický plán, ale v skutočnosti chceli tento systém využiť pre vlastné účely.