In December 1851, Major Heintzelman led the Yuma Expedition from the post of San Diego to put down the Yuma uprising, called the Yuma War. His expedition established Fort Yuma and peace was made in October, 1852. He received the brevet of lieutenant colonel for his conduct in the campaign against the Yuma Indians and on March 3, 1855, he was promoted to major of the 1st U.S. Infantry and served with that regiment on the Texas frontier. In 1859, during the First Cortina War in Texas, he was largely responsible for the defeat of Juan Cortina's forces.