Sheridan's massive campaign that first winter involved six cavalry regiments accompanied by frontier scouts "Buffalo Bill" Cody, "Wild Bill" Hickok, Ben Clark, and Jack Stillwell. Troops from the 10th Cavalry, a distinguished unit of black "Buffalo Soldiers" who constructed many of the stone buildings still surrounding the Old Post Quadrangle, camped at the new fort.

At first the garrison was called "Camp Wichita" and referred to by the Indians as "the Soldier House at Medicine Bluffs." Sheridan later named it in honor of his West Point classmate and friend, Brigadier General Joshua W. Sill, who was killed during the Civil War. The first post commander was Brevet Major General Benjamin Grierson and the first Indian agent was Colonel Albert Gallatin Boone, grandson of Daniel Boone.

Several months after the establishment of Fort Sill, President Grant approved a peace policy placing responsibility for the Southwest tribes under Quaker Indian agents. Fort Sill soldiers were restricted from taking punitive action against the Indians who interpreted this as a sign of weakness and soon resumed raiding along the the Texas frontier. However, in 1871 General William Tecumseh Sherman arrived at Fort Sill to find several Kiowa chiefs boasting about a wagon train massacre. Sherman quickly ordered their arrest and two of the Indians attempted to assassinate him.

The raiding continued; however, and without a chance to graze their livestock and faced with the disappearance of the great buffalo herds, the Comanche, Kiowa, and Southern Cheyenne Indians went on full warpath in June, 1874. As the South Plains reverberated with the hoof beats of Indian raiders, the U.S. Army retaliated with the Red River Campaign, which lasted a year, and would end in the final relocation of the Southern Plains Indians to reservations. Quannah Parker and his Quahadi Comanches were the last to abandon the struggle, and their arrival at Fort Sill's Quartermaster Corral in June, 1875 marked the end of Plains Indian warfare on the Southern Plains.

However, that would not be the end of Fort Sill's history with the Indians. In 1892, Lieutenant Hugh L. Scott organized Troop L of the 7th Cavalry, composed of Kiowa, Comanche and Apache Indians, who were credited with helping tribes on the South Plains to avert the bloody Ghost Dance uprising of the 1890s in which many died on the North Plains. Troop L, considered one of the best in the west, was the last Indian Troop in the United States Army until it was mustered out in 1897.