Na przełomie 1864 i 1865 roku został oficerem w sztabie VI Korpusu Armijnego, gdzie otrzymał stopień kapitana (niem. Hauptmann). Na tym stanowisku uczestniczył w wojnie prusko-austriackiej w tym w bitwie pod Sadową. Po zakończeniu przewodził sztabowi 11. Dywizji Piechoty. W 1868 roku objął dowództwo nad kompanią w 94. Pułku Piechoty, a już rok później został członkiem sztabu VII Korpusu Armijnego. Jako major znalazł się na froncie wojny francusko-pruskiej. Jego szlak bojowy obejmował strarcia pod Spichern, Gravelotte, oblężenie Metzu oraz bitwę pod Loigny-Poupry. Za udział w kampanii wojennej otrzymał obie klasy Krzyża Żelaznego.
W 1874 roku został dowódcą batalionu w 2. Pułku Grenadierów, a rok później otrzymał awans na podpułkownika (niem. Oberstleutnant). W szeregach 2. Pułku Grenadierów pozostawał do 1878 roku, kiedy awansował na pułkownika (niem. Oberst) i objął dowództwo nad 53. Pułku Piechoty. W 1881 roku został dowódcą 1. Pułk Grenadierów Gwardii. W 1883 roku uczestniczył w koronacji cara Aleksandra III, która odbyła się w marcu tego roku. Od 1884 roku generał major (niem. Generalmajor) von Kaltenborn-Stachau był szefem sztabu Korpusu Gwardii. Pełnił tę funkcję niecały rok, gdyż już w 1885 roku został dowódcą 2. Brygady Piechoty Gwardii.