Maximilian Coudenhove stamde uit de familie Coudenhove, die afkomstig was uit het graafschap Vlaanderen, maar de Oostenrijkse Nederlanden verliet ten tijde van de Franse Revolutie. Hij was de tweede zoon van graaf Franz Coudenhove (1774–1838), proost van het kapittel van de Vyšehrad in Praag. Zijn moeder was Charlotte Wamboldt von Umstadt.
In 1854 werd hij bevorderd tot generaal-majoor en werd hij gestationeerd in het garnizoen van Rastatt. Tien jaar later werd hij bevorderd tot veldmaarschalk-luitenant. Niet lang daarna, in januari 1865, ging hij uiteindelijk met pensioen.
