Tullahassee is considered the oldest of the surviving All-Black towns of Indian Territory. Located in Wagoner County five miles northwest of Muskogee, Tullahassee is one of more than fifty All-Black towns of Oklahoma and one of thirteen still existing. The roots of the community were planted in 1850 when the Creek Nation built a school along the ruts of the Texas Road. Near the school, the population of Creek freedmen increased while the population of Creeks declined. The council transferred the American Indian students to another school and gave Tullahassee to the freedmen on October 24, 1881. The town was incorporated in 1902 and platted in 1907. The post office was established in 1899, with a Professor Willis serving as the first postmaster. The Missouri, Kansas, and Texas Railway line ran through the town, helping to attract settlers. Community growth was aided by the Tullahassee Town Site Company, which solicited residents throughout the South. A. J. Mason served as president and L. C. Hardridge as secretary.
In 1916 the African Methodist Episcopal Church established Flipper Davis College, the only private institution for African Americans in the state, at Tullahassee. The college, which occupied the old Tullahassee Mission, was closed after the end of the 1935 session. The A. J. Mason Building is listed in the National Register of Historic Places (NR 85001743). Carter G. Woodson School is listed in the Oklahoma Landmarks Inventory as a resource related to African American history.
Tullahassee's population held steady at nearly 200 from 1920. In 1970 it dropped to 145 residents. In 2000 the town sheltered 106 citizens.Larry O'Dell, Tullahassee, in The Encyclopedia of Oklahoma History and Culture, Dianna Everett, et al., eds. (Oklahoma City: Oklahoma Historical Society, 2009), 1510 - 1511.