Das Gebiet, in dem Memphis liegt, wurde ursprünglich von den Chickasaw besiedelt. Der spanische Entdecker Hernando de Soto bereiste wahrscheinlich um 1541 die Gegend. Erste dauerhafte europäische Besiedlungsversuche gingen von Frankreich aus. Fort Proudhomme entstand 1682, Fort Assumption 1739. Nach dem englisch-französischen Krieg übernahm England die Kontrolle des Territoriums, de jure stand es zu dieser Zeit noch den Chickasaw zu. Chickasaw, Franzosen, Engländer und Spanier lebten weitgehend friedlich miteinander, bis Tennessee 1790 ein US-Territorium und schließlich 1796 US-Bundesstaat wurde. Obwohl offiziell immer noch Indianerland, zogen weiße Siedler in die Gegend, die Chickasaw gaben schließlich 1818 ihr nördliches Territorium auf, in dem das heutige Memphis liegt.
Die eigentliche Stadtgründung erfolgte 1819, als Gründungsväter gelten General und US-Präsident Andrew Jackson, General James Winchester und der Richter John Iverton. Zu diesem Zeitpunkt hatte Memphis ungefähr 50 Einwohner. Die Stadt wurde nach der Hauptstadt des antiken Ägyptens Memphis benannt. Der Sohn von Winchester wurde erster Bürgermeister. Der Aufschwung zur Großstadt begann mit der Immigration von Deutschen und Iren. Die katholische St. Mary's Church mit dem ältesten Altar der USA stammt ebenfalls aus dieser Zeit.