The post was named for Robert Field Stockton, a United States naval commodore, notable in the capture of California during the Mexican-American War. The camp was first built by troops of the 1st and 8th Infantry at a site southwest of the present location, near the town of Fort Stockton’s present Courthouse. When it was complete, it was first garrisoned by Company H of the First U.S. Infantry.

When the Civil War broke out, U.S. troops were withdrawn from the post and Confederates briefly occupied it until, they too, also withdrew. By the end of the Civil War, little remained of the first post. In July 1867, Colonel Edward Hatch, Commander of the 9th Cavalry, re-established Fort Stockton at its present location, about ½ miles northeast of the former camp. The new fort designed to be much larger and to stand more permanently, was re-established by four Companies of the 9th U.S. Cavalry Regiment, known as Buffalo Soldiers.

Encompassing 960 acres of leased property, some 35 buildings would be constructed by the troops, one of the first of which was a guardhouse, which was completed in 1868. Two of the buildings were constructed of limestone, while the rest were built of adobe.

When the 9th Cavalry was moved to New Mexico in 1875, Colonel Benjamin Grierson's 10th Cavalry took over the duties of protecting the westward migration and trade routes. Between 1867 and 1886, 87% of all the soldiers garrisoned at Fort Stockton were Buffalo Soldiers, who surmounted harsh living conditions, low pay, and racial prejudice, while also gaining a reputation for tenacity and bravery, playing a major role in the settlement and development of America's western frontier. During this period of time, the fort also provided employment and revenue for freighters, laborers, farmers, stockmen, and merchants.

The settlement that grew up around the fort would also eventually take on the name of Fort Stockton, but, not in the beginning. As the new post was being built, a number of settlers came to the area, but, it wouldn’t be until several San Antonio entrepreneurs were convinced that water from Comanche Springs, nearby Leon Springs, and the Pecos River could be used for irrigation, that it would really begin to grow. The investors purchased large tracts of land for agricultural development and in 1868, another investor named Peter Gallagher bought the land  on which Fort Stockton and Comanche Springs were located. Gallagher then platted 160 acres for a townsite that he named Saint Gaul. He also established two stores at Comanche Springs and purchased more property along Comanche Creek.