Apalachicola Province was a group or association of towns located along the lower part of the Chattahoochee River in present-day Alabama and Georgia. The Spanish so called it because they perceived it as a political entity under the leadership of the town of Apalacicola. It is believed that before the 17th century, the residents of all the Apalachicola towns spoke the Hitchiti language, although other towns whose people spoke the Muscogee language relocated among the Apalachicolas along the Chattahoochee River in the middle- to later- 17th century. All of the Apalachicola towns moved to central Georgia at the end of the 17th century, where the English called them "Ochese Creek Indians". They moved back to the Chattahoochee River after 1715, with the English then calling them "Lower Creeks" ("Lower Towns of the Muscogee Confederacy"), while the Spanish called them "Ochese".

In the first half of the 17th century, a number of towns were situated along 160 kilometres (100 mi) of the Chattahoochee River in Alabama and Georgia, from the south of the falls at present-day Columbus to Barbour County, Alabama. Archaeological evidence indicates that the material culture of the 17th century lower Chattahoochee region had developed in place over several centuries. The ancestors of at least some of the people in the area may have been there as early as 12,000 years ago. In the Middle and Late Woodland Period (300–750) sites such as Kolomoki were important centers of the regional culture. A variant of the Lamar regional culture, with influences from the Fort Walton culture to the south, developed in the towns along the Chattahoochee between 1300 and 1400. The cultural continuity of archaeological sites into historical times suggests that the towns along the Chattahoochee River spoke the Hichiti language in the late prehistoric period.

A chiefdom of the South Appalachian Mississippian culture had existed in the lower Chattahoochee River valley in the 16th century. A major change in ceramic types at sites along the Chattahoochee River occurred between 1550 and 1650. There is also evidence of a large drop in the population in the area. The de Soto expedition in the 1540s did not enter the Chattahoochee Valley, but appears to have severely disrupted the population of that chiefdom, causing many deaths there due to epidemics of European and African diseases introduced by the Spaniards. Some archaeologists state that only two population centers survived along the Chattahoochee in the late 16th century, situated on opposite sides of the river south of the falls at Columbus. Both sites had large platform mounds, and may have served as ceremonial centers. While some archaeologists believe that some sites along the Chattahoochee remained stable population centers, and became sites of later population expansion, other archaeologists believe that there were significant influxes of other people into the Chattahoochee Valley, changing the material culture of the area, and that similar processes occurred in the Tallahassee Hills region of Florida (the historic Apalachee Province). At least some of the people of the Chattahoochee River towns may have migrated south towards Apalachee, while Muscogee people from the Coosa and Tallapoosa areas in Alabama may have moved into the Chattahoochee valley. Folklore of the Lower Towns of the Muscogee Confederacy supports an interpretation of Muscogee-speaking immigrants joining a Hitchiti-speaking resident population, with the Chattahoochee River area including both Hitchiti- and Muscogee-speaking towns by the later 17th century. Speakers of the Koasati language, Apalachee people, and people known as Chisca or Yuchi also settled in the Chattahoochee towns in the later 17th century.

The collapse of the Mississippian culture that followed the disruption caused by the de Soto Expedition was incomplete. Both Foster and Hahn comment that Apalachicola Province had "the form, but not the substance, of a multi-community 'chiefdom'." Individual towns in Apalachicola Province were independent to a great extent. Bolton refers to the towns in Apalachicola Province in 1679 as the "Apalachicola Confederacy".

The Spanish contacted the towns on the Chattahoochee River in 1638, five years after Spanish missions were first established in Apalachee Province. The Spanish called the association of towns on the Chattahoochee River "Apalachicola Province",, after what they perceived as the most powerful town in the province, Apalachicola. Apalachicolas began asking for friars to be sent to them in the 1640s, and regular trade between the Spanish in Apalachee Province and the Apalachicola began in the 1650s. By the 1670s, deer skins from the Apalachicola were being shipped to Havana.

The Spanish heard of outside people moving into Apalachicola Province in the 1670s. At the same time the English adventurer Henry Woodward, who had reached the upper reaches of the Savannah River, heard reports of the "Cowatoe", the first mention of Coweta in European sources. Later the same year the bishop of Cuba produced a list of potential targets for missions, which included Coweta ("Cueta" to the Spanish) in the northern part of Apalachee Province. While Coweta later claimed to be the most ancient and powerful town on the Chattahoochee, it had only moved there in the 1660s or 1670s, into the northern end of a province consisting of at least eight Hitchiti-speaking towns. The Spanish originally perceived political power to be concentrated in the southern part of the province. The Spanish recognized Apalachicola as the most important town in the province, while Sabacola, at the southern end of the province, also exercised great influence, being closest to the Spanish in Apalachee Province. The chief of Sabacola may have converted to Christianity, and was recognized by the Spanish at one point as the "grand cacique" of Apalachicola Province.

The number and names of towns on the Chattahoochee River varied in different Spanish reports. Two lists, from 1675 and 1685–1686, show many similarities, and a few differences. The towns listed by the Spanish, from south to north, were:

Three towns that were on or close to the route of de Soto's expedition in 1540 may have later moved to the Chattahoochee River. Alapi may have derived from a town located east of Cofitachequi, the town of Ocuti may have been a successor to the Ocute chiefdom of the Oconee River valley, and Casista (Kasihta) was on the Coosa River at the time of de Soto's visit.