Crittenden had brief duty as a private in the Kentucky Infantry in 1836 when war with Mexico seemed possible. During the Mexican War a decade later, as an aide on the staff of General Zachary Taylor, Crittenden was selected to carry news of the victory at Buena Vista to President James K. Polk. Crittenden then served as lieutenant colonel of the Third Kentucky Infantry in which John C. Breckinridge was major. The regiment joined General Winfield Scott's army after Mexico City was captured.