The Natchez Native Americans from the Caddoian Mississipian culture were the first residents of Concordia Parish. Spain owned the land at the time that Europeans began to filter into the area, including the Spanish town of Natchez in the Mississippi Territory just across the Mississippi river from the future Concordia Parish. About 1798, Don Jose Vidal (b. March 12, 1763, in A Coruña, Spain), received land grants from the Spanish Government which were located on the Lousiana side of the Mississippi River from Natchez. He was at that time secretary to Manuel Gayoso de Lemos, the Spanish Governor of the Natchez District. He moved his family across the river and became the Commandant of a new Post of Concordia for the Spanish. Concordia Parish derives it's name from from the fort (the name "Concordia" comes from a Latin word meaning "harmony") and a town that developed was called Concord. The name of the town, Concord, was changed in 1811 to Vidalia by order of the Orleans Territorial government.

Concordia County was officially formed in 1804 after the 1803 Louisiana Purchase. It was one of 13 counties designated as such by the Legislative Council of the Orleans Territory. In 1807 the counties in Orleans Territory were changed to Parishes due to the influence of the Catholic Churches in the territory. Concord, later Vidalia, became the parish seat of government of Concordia Parish. Louisiana did not officially become a state of the United States until April 30, 1812.