The gallows proper had their beginning in early August of 1873. The Fort Smith Weekly New Era of August 6, 1873, reported that "Captain C. E. Perry, U.S. Jailer has received orders to erect the gallows for the execution of prisoners sentenced to be hung here shortly." The article also noted "the fatal structure may already be seen going up near the old powder magazine just inside the garrison walls." The only other known description of the location of the first gallows was published in the New Era of August 20, 1873, which placed the scaffold "at the opposite end of the grounds near the magazine."
The area in which the gallows stood was the southwestern corner of the five-sided fort. Each of the corners was to have been originally crowned with a blockhouse or bastion. When the fort's role was changed in the 1840s from that of a frontier defense to a supply depot it was decided to utilize these sturdy foundations for more practical structures. Therefore the foundations of bastion #1 (Northwestern corner) were modified and a two-story stone commissary warehouse constructed upon them. The Southwestern bastion (#2) was later crowned with a very similar structure housing the quartermaster warehouse. In September of 1846, Colonel Arbuckle negotiated a contract which converted the southern blockhouse foundation (bastion #3) into a very sturdy magazine for the storage of munitions. It was against the face of this structure that the two successive gallows were constructed. In October of 1873, after the final closure of Fort Smith by the army, three commissioners appointed by the Secretary of Interior to appraise the buildings of the fort described the structure as follows:
Pentagonal (Magazine) Stone 2 faces 30 ft. 2 faces 20 ½ ft., one 15 ft. used for storage of powder belonging to citizens. Good condition. Valuation - $400
In September 1875, at the first execution carried out after Judge Parker’s arrival in Fort Smith, an extra edition of the Independent described the building and area: "In one corner of this wall stands an old pentagon-shaped building, with iron doors and pointed roof, built of solid masonry…."