Wallace was born in Lexington, Virginia, to parents of Scots-Irish descent. When he learned that a brother and a cousin had been killed in the Goliad Massacre, he set out for Texas to "take pay out of the Mexicans"; years later, he confessed that he believed the account had been squared. Wallace was a large man at 6'2" and 240 pounds in his prime.
In the 1850s, Wallace commanded a ranger company of his own, fighting border bandits as well as Native Americans. He was so expert at trailing that he was frequently called upon to track down runaway slaves trying to get to Mexico. He drove a mail hack from San Antonio to El Paso and on one occasion, after losing his mules to Comanches, walked to El Paso and ate twenty-seven eggs at the first Mexican house he came to before going on to town for a full meal.
During the Civil War, he helped guard the frontier against Comanches. At one time, Wallace had a small ranch on the Medina River on land granted to him by the state of Texas.
The later years of his life were spent in South Texas in the vicinity of a small village named Bigfoot. He never married. He was a mellow and convivial soul who liked to sit in a roomy rawhide-bottomed chair in the shade of his shanty and tell the stories of his career. Wallace was personally honest but liked to "stretch the blanket" and embellish his stories.
Wallace died on January 7, 1899, and shortly thereafter the Texas legislature appropriated money for moving his body to the Texas State Cemetery.
