Другой брат, Александр фон Штауффенберг, преподавал древнюю историю. Во время войны профессор Штауффенберг служил на фронте, был ранен. 11 августа 1937 года он женился на знаменитой летчице Мелитте Шиллер. Она окончила Мюнхенский технологический институт, занималась разработкой и испытанием навигационного оборудования. Ее щедро награждали орденами.
Но выяснилось, что отец Мелитты происходил из еврейской семьи из Лейпцига. Он перешел в лютеранство, служил в прусской армии, но органы госбезопасности сигнализировали о присутствии чужой крови. Мелитта и ее родственники оказались в опасности. Но поскольку ее работа была признана имеющей военное значение, Гитлер по просьбе министра авиации Германа Геринга в 1944 году подписал документ, приравнявший графиню Мелитту Шенк фон Штауффенберг к арийке. Это спасло всю семью от концлагеря.
25 июня 1938 года капитан Клаус Шенк фон Штауффенберг окончил академию с репутацией одного из самых блестящих офицеров. 1 августа получил назначение в штаб 1-й легкой дивизии в Вуппертале. Это была одна из первых четырех танковых дивизий вермахта, командовал ею Эрих Хёпнер, еще один будущий участник антигитлеровского заговора. В апреле 1939 года 1-я дивизия получила двести пятьдесят трофейных чехословацких танков.
Семья переехала к Штауффенбергу. Жена и дети были рядом. Он подружился с офицерами штаба. Самостоятельный и открытый человек без двойного дна, он неизменно вызывал симпатии окружающих. Но Вупперталь он не любил: "Невообразимо пролетарский, здесь невозможно существовать".
Вторая мировая началась для него 1 сентября 1939 года. В первый же день войны дивизия вступила в бой с польскими войсками. 2 сентября в пять утра передовые части дивизии вошли в город Вилун. Штауффенберг писал семье:
"Страна мрачная, сплошной песок и пыль, удивительно, что здесь что-то растет. Местное население — ужасный сброд, очень много евреев и людей смешанной крови. Это люди, которые привыкли, что ими управляют с помощью кнута. Тысячи пленных пригодятся нашему сельскому хозяйству. В Германии им найдут хорошее применение. Они будут трудиться усердно и охотно".
Известие о том, что 3 сентября Англия и Франция объявили войну Германии, вызвало у офицеров подавленность. Такого шага они не ожидали. Штауффенберг сказал, что теперь война продлится лет десять.
За девять дней дивизия вторглась в глубь польской территории на двести километров. 13 сентября Штауффенберг писал жене: "Невероятно быстрый марш вперед создает трудности в снабжении наших войск. Наши запасы исчерпаны".
Чем большими были успехи немецких войск, тем более Штауффенбергу нравилась война. 29 сентября Варшава пала. Штауффенберг писал домой: "Важно, чтобы мы начали в Польше планомерную колонизацию".
12 октября дивизия вернулась на прежнее место дислокации. Ее переформировали в 6-ю танковую. Штауффенберг был вдохновлен польским походом и пребывал в радостном ожидании новых боев. Но его, аристократа, раздражали речи партийного пропагандиста Йозефа Геббельса, который утверждал, что солдаты вермахта сражаются лучше средневековых рыцарей, потому что воюют за хлеб и жизненное пространство, а не за какие-то идеалы.
Дивизию Штауффенберга перебросили на Западный фронт. 10 мая 1940 года 6-я танковая дивизия двинулась вперед через Арденны. От успеха танкистов Эриха Хёпнера зависел успех всей кампании. За девять дней танки преодолели двести семьдесят километров.
"Мы в отличной форме, — писал Штауффенберг жене. — Мы свидетели конца Франции. Не только военного, но и психологического. Не знаю, следишь ли ты за событиями. Неслыханный успех, неудержимый бросок! Французы даже не проявляют желания сопротивляться. Они сдаются тысячами".
Французская армия капитулировала. Британские войска эвакуировали на родину.
27 мая охваченный восторгом победы Штауффеиберг написал жене: "Если англичане не уступят, нам придется уничтожить Англию".
В этот самый день Штауффенберг получил назначение, которому многие бы позавидовали. Его перевели во 2-е (организационное) управление Генерального штаба сухопутных войск. Командование давно к нему присматривалось. А он не желал этого перевода. Не хотелось покидать дивизию в момент победы. 31 мая он получил Железный крест первого класса и попрощался с товарищами. Отпустили его из дивизии неохотно. Ему было тридцать два года.
В Генштабе он занимался обучением и переформированием частей, подготовкой резервов. Штауффенберга высоко ценили, строевые командиры просили его о помощи, поскольку не могли пробиться к начальству. 1 января 1941 года его произвели в майоры. Здесь он увидел хаотический характер управления вермахтом. Неделями Генштаб занимался исполнением приказов Гитлера, которые часто оказывались бессмысленными.