Pendant la guerre des Duchés, il fait partie de la commission des chemins de fer. En , il intègre l'état-major du 6e corps d'armée. Il est promu capitaine en 1865 et c'est à ce poste qu'il prend part à la guerre contre l'Autriche en 1866. Deux ans plus tard, il est chef de compagnie au 94e régiment d'infanterie puis en 1869 officier d'état-major au 7e corps d'armée.
Le , il est nommé à la succession de Julius von Verdy du Vernois en tant que ministre de la Guerre. C'est sous son mandat, en 1893, que l'armée est élargie à 70 000 hommes en l'espace de deux ans. Kaltenborn-Stachau se retire de son poste le .