Dokładna data powstania miasta jest trudna do ustalenia. W czasach przed chrystianizacją Danii istniało tutaj miejsce kultu Odyna, od którego miasto wzięło swoją nazwę. Pierwsze dokumenty, w których Odense jest wzmiankowane, pochodzą z 988 r. (przywileje cesarza Ottona III dla nowo powstałego biskupstwa w Odense). Kronikarz Adam z Bremy opisał w latach 70. XI w. Odense jako wielkie miasto[1]. Wydarzeniem, które odcisnęło bardzo wyraźne piętno na historii miasta, było zamordowanie króla Danii i późniejszego świętego, Kanuta w 1086 r. Król został zabity wraz ze swoim bratem Benedyktem i towarzyszącymi mu osobami przed ołtarzem ówczesnego kościoła św. Albana. W 1101 r. Kanut został kanonizowany, a kościół w którym poniósł śmierć nazwano jego imieniem. Wkrótce przy kościele, który stał się miejscem pielgrzymek wiernych, powstał klasztor benedyktyński, a po nim wiele innych. W średniowieczu Odense było otoczone wałami obronnymi i fosą, a dostęp do miasta prowadził przez bramy. Na początku XVI w. królowa Danii Krystyna saska obrała sobie za siedzibę Odense. Rezydowała ze swoim dworem na zamku Næsbyhoved koło miasta, ale i w samym Odense miała również swoją siedzibę. Tutaj też zmarła w 1521 r.

W 1803 r. wykopano kanał łączący miasto z fiordem, co było od dawna oczekiwaną inwestycją, ponieważ od XVI w. Odense było ważnym ośrodkiem handlowym i dotkliwie odczuwało brak bezpośredniego dostępu do morza. Szczególny rozwój miasta nastąpił w XVIII w. z powodu korzystnych kontaktów handlowych z Lubeką i Norwegią. W 1805 r. w Odense urodził się Hans Christian Andersen. Wiek XIX oraz XX zaznaczyły się raptowną industrializacją miasta oraz dalszym rozwojem handlu, na co m.in. wpłynęło wybudowanie linii kolejowej łączącej Odense z Jutlandią i Zelandią w 1865 r. Odense było pierwszym miastem na duńskiej prowincji, które otrzymało oświetlenie gazowe ulic, kanalizację oraz elektryczność. W latach 1940–1945 okupowane przez Niemców. Po wprowadzeniu stanu wyjątkowego w sierpniu 1943 r. w mieście doszło do potyczek ze stacjonującymi tutaj Niemcami. Wyzwolone w maju 1945 r. przez duński ruch oporu i wojska brytyjskie. Od 1966 r. Odense jest miastem uniwersyteckim.