In 1845, McCulloch was elected from Gonzales County to the first Texas state legislature following its entry into the union. In the spring of 1846, a law was passed appointing him Major General in command of all Texas militia west of the Colorado River. That same year, with the outbreak of the war with Mexico, he raised a company of Rangers that became Company A of Col. Hays's 1st Regiment of Texas Mounted Volunteers, who were known for their ability to regularly travel 250 miles in ten days or less. He subsequently was named chief of scouts under Gen. Zachary Taylor, with the rank of major, and became known nationwide for his daring exploits in northern Mexico. (His company of scouts included George Wilkins Kendall, editor of the New Orleans "Picayune".) By this time, McCulloch was fluent in Spanish and his woodsman's skills enabled him to slip back and forth across the lines undetected—more than once penetrating to within a mile of Santa Anna's own tent.