[1][2] Willis was born on January 9, 1831, in New York City and when he was nineteen he traveled west for the California Gold Rush.

From San Diego, Willis marched with James H. Carleton's expedition across New Mexico Territory and was involved in the capture of Tucson, an old Spanish presidio defended by a handful of militia.

In September, Willis led a scouting party against the Navajo and later was on the board to determine where to build Fort Whipple.

In January 1866 Willis was in command of Fort Selden when he heard a rumor that a large band of Apaches had sacked the Janos presidio in Chihuahua.

He then became a civil engineer in New Mexico, Arizona California, Oregon, Washington and Oklahoma Territory before retiring to Omaha, Nebraska.