Von ca. 4000 v. Chr. bis etwa 1350 siedelten die Sinagua-Indianer in ihren Pueblos im Verde Valley. Ab 1400 folgten die Yavapai und Apachen. Die ersten Europäer in diesem Gebiet waren die spanischen Goldsucher Antonio de Espejo (1583) und Marcos Farfan de los Godas (1598). Sie fanden jedoch kein Gold, sondern Kupfer.

Bis 1821 gehörte das Land zu Spanien und ging dann in den Besitz von Mexiko über. 1848 fiel es nach dem Vertrag von Guadalupe Hidalgo, der dem Mexikanisch-Amerikanischen Krieg folgte, an die USA und gehörte nunmehr zum Bundesstaat Arizona.

1876 traf mit John James Thomson der erste Siedler in der Gegend ein. Sedona wurde am 26. Juni 1902 als Farmerdorf gegründet und bekam im Januar 1988 die Stadtrechte. Der Name der Stadt stammt von der Ehefrau von Theodore Carleton „T.C.“ Schnebly, der um 1899 im Ort eine Poststation eröffnet hatte. Die Poststation hieß zunächst Oak Creek Crossing and Schnebly Station. Da der Postverwaltung der Name zu lang war, gab Schnebly den Namen seiner Frau Sedona an.

Mit den surrealistischen Künstlern Dorothea Tanning und Max Ernst, die 1946 nach Sedona zogen, wurden bald schon Maler, Bildhauer, Schriftsteller und Angehörige anderer kreativer Berufe angezogen, die das Stadtbild signifikant prägen. Ernst schuf hier 1948 seine Großplastik Capricorn aus Zement, die vor seinem Haus stand. Sie ist nur noch in Fragmenten erhalten, die sich in Berlin befinden. Es existieren jedoch eine Abformung in Gips und einige Bronzegüsse an verschiedenen Orten.

1946 erbaute das Hollywood-Studio Republic Pictures eine Filmranch in Sedona, um vor dieser besonderen Kulisse insgesamt über 60 Westernfilme zu drehen. Darunter Der schwarze Reiter (1947) mit John Wayne, Desert Fury – Liebe gewinnt (1948) mit Burt Lancaster, Gun Man (1948) mit Robert Mitchum sowie der Klassiker Johnny Guitar – Wenn Frauen hassen (1955) mit Joan Crawford, der besonders stark von Landschaftsaufnahmen Gebrauch machte. Nachdem Republic in den 1960er-Jahren in Konkurs ging, kaufte der amerikanische Fernsehsender CBS das Gelände, um dort Fernsehproduktionen zu drehen.[1] 2020 wurde ein Marskrater nach Sedona benannt.[2]