Grief stricken, Vermillion headed westward and by the late 1870’s he was in Dodge City, Kansas where he was known to have drank heavily, gambled often, and gained a reputation as a gunfighter. There he made the acquaintance of Virgil Earp, Wyatt Earp, and Doc Holliday.

A couple of years later, he was in Tombstone, Arizona, working as a special policeman for Virgil Earp in 1881. After the Gunfight at the O.K. Corral in October, 1881, and Morgan's murder in March, 1882, Wyatt and Warren Earp, along with Doc Holliday, escorted the Earp family out of town before going on the well-known Earp Vendetta Ride, of which Vermillion was a part.

The next year, Luke Short, who was in Dodge City, Kansas and in a feud with other business men there, called upon Bat Masterson for help. Bat rounded up several gunfighters including Wyatt Earp and Jack Vermillion in what is known as the Dodge City War. Though the “war” never actually wound up violent, it threatened to be as some of the Old West's best known gunfighters lined up in support of Short.

While Vermillion was in Dodge City, he shot and killed a gambler who was cheating at cards, after which he appeared on a wanted poster as “Texas Jack Vermillion.”  Where the “Texas” part came in is unknown. According to one tale, when Vermillion was asked why he was called Texas Jack, he replied "Because I'm from Virginia." Later, he also became known as "Shoot-Your-Eye-Out" Vermillion, allegedly because he had shot the man in the eye.

Soon, Vermillion was back in his home state of Virginia, where he married a woman named Nannie Fleenor in 1883 and had two children.

However, history finds him back in the west by 1888, where he joined up with Soapy Smith and his gang of con artists in 1888 in Denver, Colorado. In August, 1889, he was with Soapy, Bascomb Smith, and "Fatty Gray" Morris at the Pocatello, Idaho. There, a rival bunco gang tried to assassinate Soapy and a shootout occurred at the train depot.