Additional quarters were built outside the original fort in 1822 when increased hostilities between the Osage and Cherokee prompted the need for a greater number of soldiers. Just two years later; however, the Federal Government determined that the location of the fort was too far away from the  newly redefined Indian Territory (Oklahoma) and established Fort Gibson some 60 miles up the Arkansas River. As a result, the troops departed Fort Smith in 1824.

Three years later; however, the fort was slated to serve as the agency for the western Choctaw Indians, who were also being forced to move to Indian Territory. When Choctaw agent, William McClellan, arrived in February, 1827, he found the post buildings in bad condition. But, it would be four more years before the government would repair the structures. Finally, in April, 1831, Lieutenant Gabriel Rains and a detail of Seventh United States Infantry arrived at the post to begin the repairs. By August, Choctaw Indians began trickling into the area.

Just east of the post and adjacent to the Choctaw boundary line, a sizeable civilian community emerged on lands owned by a man named John Rogers. Dominating the community were six taverns, where enterprising merchants supplied the emigrating Choctaw with cheap whiskey. Many of the displaced tribesmen settled nearby and became a source of sustained exploitation. Lieutenant Rains positioned his men on the boundary line to keep peddlers and Choctaw separated, but the situation got worse. In March, 1833, Captain John Stewart and a company of Seventh Infantry were garrisoned at the post to control the contraband trade, known as the "Arkansas Whiskey War." He too, met with little success as the merchants operated right under his very nose. As a result, Stuart abandoned Fort Smith in June 1834 and established Fort Coffee at a more suitable location in Indian Territory.

As additional tribes were relocated in Indian Territory, fearful residents of the new State of Arkansas requested that a permanent military garrison be placed on their western border. In 1838, Congress authorized construction of a new fort and purchased from John Rogers a 296-acre reservation adjacent to the old fort on Belle Point.

In the spring of 1839, construction of the new fort began. The design called for a pentagonal-shaped fort of stone with a bastion at each angle and enclosing seven acres. Inside the wall, several buildings were to be situated around a parade ground including two enlisted mens barracks, two officer’s quarters, the commandant’s quarters, a hospital, the quartermaster store, and other buildings. This ambitious plan, however, would never be fully realized.