ชเตาเฟินแบร์คได้ติดยศร้อยตรีในปีค.ศ. 1930 ชเตาเฟินแบร์คมีความคิดเห็นด้วยกับนโยบายชาติพันธุ์และชาตินิยมของพรรคนาซี และเขาสนับสนุนการบุกยึดโปแลนด์[4][5][6] เขายังลงคะแนนเสียงให้ฮิตเลอร์ในการเลือกตั้งประธานาธิบดี ค.ศ. 1932 กระนั้น เขาไม่เคยเป็นสมาชิกพรรคนาซี และคัดค้านนโยบายอื่นหลายอย่างของฮิตเลอร์ อาจกล่าวได้ว่าในจุดนี้เขาทั้งรักทั้งชังฮิตเลอร์ เหตุการณ์ที่ทำให้ชเตาเฟินแบร์คถอยห่างออกมาจากพรรคนาซีอย่างไม่มีวันกลับคือคืนมีดยาวและคืนกระจกแตก เขามองว่าฮิตเลอร์เป็นคนไร้คุณธรรม นอกจากนี้ การกดขี่ชาวยิวอย่างรุนแรงและการกดขี่ศาสนาได้ขัดแย้งกับหลักศีลธรรมในใจของชเตาเฟินแบร์ค เนื่องจากครอบครัวของชเตาเฟินแบร์คมีความศรัทธาต่อคาทอลิกอย่างเคร่งครัด[7][8]

เมื่อสงครามโลกครั้งที่สองปะทุขึ้นในปีค.ศ. 1939 ชเตาเฟินแบร์คและหน่วยของเขามีส่วนร่วมในการบุกครองโปแลนด์ เขาสนับสนุนให้เยอรมนียึดครองโปแลนด์และใช้ชาวยิวเป็นทาสแรงงานเพื่อความรุ่งเรืองของเยอรมนี[4] เมื่อเสร็จศึกโปแลนด์ ชเตาเฟินแบร์คเริ่มรับรู้ถึงความเลวร้ายของระบอบนาซี ลุงของเขาสังเกตเห็นได้จึงพยายามโน้มน้าวให้เข้าร่วมกับขบวนการต่อต้านนาซี เขาถูกร้องขอให้เป็นทหารผู้ช่วยของจอมพลวัลเทอร์ ฟ็อน เบราคิทช์ ผู้บัญชาการใหญ่กองทัพบกในขณะนั้น เพื่อร่วมวางแผนรัฐประหาร ชเตาเฟินแบร์คปฏิเสธโดยอ้างว่าทหารทุกนายได้ปฏิญาณความภักดีต่อฮิตเลอร์ไปแล้วในค.ศ. 1934[9]

ต่อมาเขาได้ถูกย้ายไปสังกัดหน่วยขึ้นตรงกองบัญชาการใหญ่กองทัพบกในช่วงสงครามลวง ในตอนนี้เขายังไม่ได้คิดวางแผนรัฐประหารใดๆ แต่พี่ชายสองคนของชเตาเฟินแบร์คเริ่มติดต่อกับฝ่ายต่อต้านทั้งพลเรือนและทหารแล้ว ชเตาเฟินแบร์คถูกโอนย้ายไปสังกัดกองพลยานเกราะที่ 6 และทำหน้าที่เป็นนายทหารเสนาธิการในช่วงยุทธการที่ฝรั่งเศส ในช่วงนี้เขาได้รับกางเขนเหล็กชั้นหนึ่ง[10] ในปีค.ศ. 1943 ชเตาเฟินแบร์คในยศพันโทถูกส่งตัวไปปฏิบัติหน้านายทหารเสนาธิการของกองทัพน้อยแอฟริกาที่ประเทศตูนีเซีย เขาได้รับบาดเจ็บในสนามรบที่นี่ โดยสูญเสียตาซ้าย, แขนขวา, และสองนิ้วมือซ้าย[11]

หลังพักรักษาตัวอยู่หลายเดือน ในเดือนกันยายน ค.ศ. 1943 ชเตาเฟินแบร์คได้รับการจัดแจงโดยทหารระดับสูงในฝ่ายต่อต้านให้เป็นนายทหารเสนาธิการประจำกองบัญชาการกองทัพสำรอง (Ersatzheer) ซึ่งตั้งอยู่ในกรุงเบอร์ลิน จนกระทั่งเดือนมิถุนายน ค.ศ. 1944 เขาได้เลื่อนยศเป็นพันเอกและได้ตำแหน่งใหม่เป็นเสนาธิการของพลเอกอาวุโสฟรีดริช ฟร็อม ผู้บัญชาการกองทัพสำรอง[12] เมื่อได้ดำรงตำแหน่งนี้ สิ่งแรกที่เขาทำคือการนำร่างปฏิบัติการวัลคือเรอฉบับแก้ไข(เพื่อใช้ก่อรัฐประหาร)ไปขออนุมัติต่อฮิตเลอร์