After having fought in the Civil War, Heise re-enlisted in the army, and faced an opponent quite different in character to the Confederate Army. The rapidly settling post-war Arizona territory, where silver had been discovered, attracted miners and adventurers whose presence was not welcomed by the Hualapai Apachi, referred to as the Pais Indians. In 1866, the Pais began raiding transportation routes between Prescott, Arizona, and Colorado River settlements. The war consisted of various hit-and-run attacks, reprisals and counter-reprisals, and no shortage of brutalities rendered upon both sides. The Pais would swoop and destroy wagons and stone miners to death in the mineshafts. Cavalry detachments would destroy Pais dwellings and farms and capture women and children.

For three days beginning September 9, 1868, Lieutenant Somerby, Heise’s commander, led seventeen men who encountered bands of Pais, killing some warriors, capturing women, and destroying large amounts of Pais food and equipment. A few days later they skirmished with a band of Tonto Apaches. Heise’s exact actions in these and similar other engagements are unknown. During his Indian war service, Heise sustained his share of wounds from combat. An Indian shot him near his knee and arrow wounds in his legs left him with numerous scars.

The following comes from a letter presumably commending Heise and others before Heise was awarded the Medal of Honor. The troopers:

“spent the greater portion of every twenty-four hours in the saddle, and were exposed to the treacherous fire of the Indians, nevertheless persistently kept at them until they finally drove them into subjugation.”

The letter written from Fort Whipple continues:

“I recommend that some action be taken by the Commanding General, showing them that their services deserve special notice, and are fully appreciated…”

A year after Heise’s actions, he received his medal through express mail.