Construction began in May 1814, when British Colonel Edward Nicolls seized a trading post belonging to John Forbes and Company on the Apalachicola River. The site commanded a high bluff overlooking the water, and by September it had become the largest structure between St. Augustine and Pensacola. A square moat enclosed a field of several acres. A wooden stockade ran the length of the moat, with bastions at its eastern corners. Inside stood stone barracks, a large warehouse, and an octagonal blockhouse that served as the powder magazine, stocked with 73 kegs of gunpowder and 2,500 muskets. The British recruited Creek, Seminole, and Black settlers along the river, distributing weapons and uniforms. Enslaved Africans from Spanish Pensacola arrived by the hundreds. At its peak, Nicolls commanded some 3,500 men at Prospect Bluff, a formidable force assembled at the edge of the American frontier.

Fugitive enslaved people had been seeking freedom in Florida for generations. The Seminoles received them as allies. The Spanish treated them as free if they converted to Catholicism. What emerged along the Apalachicola River was a remarkable community: formerly enslaved people who used farming skills learned on plantations to establish settlements stretching for miles along the riverbank. They raised crops of peas, beans, corn, and rice, lived in well-built cabins, and taught agricultural techniques to the Seminoles. This network of free Black settlements, scholars have noted, represented the origins of the Underground Railroad, except that it ran south rather than north. When the British withdrew in May 1815, Colonel Nicolls left behind every weapon, every tool, every cannon. He encouraged the formerly enslaved people to recruit others to escape their owners and join the community. The fort flew the British Union Jack, as the former Colonial Marines who garrisoned it considered themselves British subjects.

Word of a fortified, well-armed sanctuary for escaped enslaved people spread through the southern United States like fire. The Savannah Journal demanded to know how long "this evil, requiring immediate remedy" would be permitted to exist. People fled to the fort from as far as Virginia. Raiders based along the Apalachicola attacked Georgia plantations, liberating enslaved workers and stealing livestock. The fort's three leaders were former Colonial Marines: Garcon, a 30-year-old carpenter formerly enslaved in Pensacola; Prince, 26, a master carpenter who had received an officer's commission from the British; and Cyrus, 26, also a carpenter and notably literate. Southern slaveholders viewed the fort as an existential threat, fearing that any foothold of Black freedom could unravel the entire institution of slavery, just as the Haitian Revolution had done in the Caribbean.

In April 1816, the U.S. Army began building Fort Scott on the Flint River, and supply boats heading to the new fort had to pass directly in front of the Negro Fort. When the fort's defenders ambushed a watering party, killing three sailors and capturing a fourth who was burned alive, the United States had its justification. Andrew Jackson ordered the fort destroyed. On July 27, Lieutenant Colonel Duncan Clinch and Creek allies approached by land while gunboats under Sailing Master Jarius Loomis moved upriver. The fort held about 330 people: at least 200 armed maroons, some thirty Seminole and Choctaw warriors, and the remainder women and children. The ninth cannonball, heated red-hot in a ship's furnace, crashed into the powder magazine. The blast killed most of the defenders. Of the roughly 330 people inside, about 270 were killed instantly, and many of the surviving sixty were mortally wounded. Secretary of State John Quincy Adams later called the fort "a seat of banditti and the receptacle for runaway slaves," using its destruction to justify Jackson's eventual seizure of Spanish Florida.

The survivors scattered. The largest group, including Black settlers from surrounding plantations, moved east to the Suwannee River valley and rebuilt near Bowlegs Town. Others took refuge in the Tampa Bay area. Garcon was executed by firing squad. The Choctaw chief was handed over to Creek allies, who scalped him. Some survivors were placed into slavery under the claim that Georgia slaveholders had owned their ancestors. But the destruction of the fort did not end resistance. Seminole leader Neamathla, enraged by the deaths of his people, warned U.S. forces that any crossing of the Flint River would be met with force. In November 1817, that warning became the opening battle of the First Seminole War. In 1818, Jackson ordered Lieutenant James Gadsden to build a new, smaller fort on the same bluff. Fort Gadsden lasted only until 1821, when Florida became a U.S. territory and the border it guarded ceased to exist.