Fort Quitman was eighty miles below El Paso and twenty miles southeast of the site of present-day McNary in far southern Hudspeth County. On September 28, 1858, Capt. Arthur T. Lee and companies C and H, Eighth Infantry, established the post on a barren and sandy plain 400 yards east of the Rio Grande to protect travelers and mail along the route from San Antonio to El Paso. It was named for Mexican War general John A. Quitman, who had died on July 17. Federal troops evacuated Fort Quitman on April 5, 1861. During the Civil War the post was intermittently garrisoned by Confederate and Union detachments and quickly fell into disrepair. Capt. Henry Carroll and Company F, Ninth United States Cavalry, reoccupied the crumbling adobe buildings on January 1, 1868, and on February 25 orders from headquarters of the District of Texas reestablished the fort. Over the next decade companies and detachments of black soldiers of the Ninth Cavalry and the Twenty-fifth United States Infantry guarded the mails and scouted for hostile Indians.
Fort Quitman had a reputation as one of the most uncomfortable military installations in Texas. Lydia Spencer Lane described it in 1869 as "forlorn and tumble-down" and was surprised to observe a sergeant, in full-dress uniform, jumping rope outside the guardhouse. "If any one at Quitman could feel cheerful enough to enjoy so innocent a pastime," she concluded, "he was to be congratulated." Surgeon John J. Culver was more blunt in his assessment of conditions at Fort Quitman (1870), which he found "entirely unworthy of the name of fort, post, or station for United States troops." The adobe buildings had been stripped of all wood, including roofs, doors, and window frames. "The dormitories of the barracks," he sarcastically commented, "having neither doors or windows, have abundant ventilation." The sandy soil and dry hot climate frustrated attempts to cultivate a post garden. Consequently, milk and fresh vegetables had to be hauled in at exorbitant prices from San Elizario, El Paso, or San Ignacio, Chihuahua. Soldiers at Fort Quitman spent considerable time repairing the buildings, which by 1876 consisted of barracks for two companies, five sets of double officers' quarters, an adjutant's office, a hospital, a guardhouse, two storehouses, a bakery, workshops, and wooden cavalry and quartermaster's stables.
Fort Quitman was vacated on January 5, 1877, but was regarrisoned in 1880–82, during the campaign against the Apache chief Victorio, as a subpost of Fort Davis. Despite the efforts of Capt. Nicholas Nolan and troopers of the Tenth United States Cavalry, during the summer of 1880 Victorio's warriors crossed and recrossed the Rio Grande in the vicinity of the post. Also, on August 9, Mescaleros attempting to return to their reservation in New Mexico attacked a stagecoach near the fort, mortally wounding Maj. Gen. James J. Byrne, an employee of the Texas and Pacific Railway. Although Victorio was killed in Mexico in the fall of 1880, Fort Quitman continued to be garrisoned through April 1882. The post was abandoned later that year, partly because it was not on a railroad. Fort Hancock (originally Fort Rice) was established in 1882 at a better site nearby. Today only a cemetery remains near the site of Fort Quitman.