At the start of the Mexican War, McCulloch raised a company of volunteers. They became Company A of Colonel Jack Hays' First Regiment, Texas Mounted volunteers. With his skills in tracking and scouting, he was soon named General Zachary Taylor's chief of scouts. He fought at the battles of Monterey and Buena Vista. When the war ended he held the rank of major.