Jeho rodičia boli prísnymi katolíkmi a boli velmi vzdelaní. Claus von Stauffenberg vyrastal v impozantnom renesančnom zámku. Vynikal v športe a v štúdiu a jeho vášeň k jazde na koni ho priviedla do nemeckého olympijského týmu. Študoval umenie a literatúru, ovládal dokonale gréčtinu a latinu. V okolí Stuttgartu žilo veľa profesorov, spisovatelov, filozofov a ludí s rôznymi špecifickými záujmami. Toto prostredie ovplyvnilo Stauffenbergovy názory a postoje a jeho vzťah ku katolíckej cirkvi. Uvádza sa, že bol ovplivnený nemeckým básnikom Stefanem Georgem, ale tento vplyv sa niekedy zveličuje. Stauffenberg sa chcel nejaký čas venovať hudbe, potom uvažoval o štúdiu architektúry, ale neskôr vo svých 19 rokoch vstúpil do armády. Nastúpil ako dôstojnícky kadet k 17. jazdeckému pluku. V dobe hospodárskej krízi v Nemecku a nástupu nacismu bol Stauffenberg apolitickým dôstojníkom. V roku 1930 sa zoznámil s Ninou von Lerchenfeld z bavorskej šlachtickej rodiny a po trojročných zásnubách sa oženil. V roku 1934 se rodine narodil první syn. O dva roky bol Stauffenberg prevelený na Vojnovú akadémiu do Berlína, kde upútal svojich nadriadených svojimi schopnosťami. Vo svojich 29 rokoch sa stal dôstojníkom vrchného velenia. Clauss von Stauffenberg nebol jedním z prvích přívržencov Adolfa Hitlera ako sa niekedy uvádza. Franz Ludwig Schenk uviedol, že otec nebol od začiatku odporcom nového systému, ale ani nebol jeho horlivým prívržencom. V 30. rokoch 20. storočia sa nestaval na odpor nastupujúcim nacistom, ale tiež nacistov neprenasledoval. Prvé pochybnosti o nacistickom programu začal mat v roku 1938, kedy došlo k silnej antisemitskej kampani. V septembri 1939, kedy začala vojna proti Poľsku, si Štauffenberg prial splniť svoju povinnosť. Svoje úlohy zvládal s pre neho charakteristickou energiou a talentom. Ako dôstojník 6. obrnenej divízie si získal pri operáciách v Polsku a vo Francúzsku dobrú povesť. V lete 1940 byl prevelený na vrchné velitelstvo a prvých osemnásť mesiacov operácie Barbarossa, strávil väčšinou na ruskom území. Tam tiež spoznal brutalitu a bezohľadnosť jednotiek SS. Behom ruského ťaženia stratil všetky ilúzie o Tretej ríši. Počas služby na ruskej fronte mal Stauffenberg dovolenku na všetky sviatky. Návštevy rodiny počas dovolenky boly pre neho vítanou zmenou a možnosťou zabudnúť na stále sa zhoršujúcu situáciu na východnom fronte. Porážka Nemcov pri Stalingrade vo februári 1943 ešte viac utvrdil Stauffenbergův velmi kritický názor na Hitlerovu vojenskú stratégiu.