Город появился на холме Монлор (cat. Montlaurès), расположенном к северо-западу от нынешнего города Нарбона, возможно, здесь обитало племя элисиков.
Первое городское поселение относится к VI в. до н.э., оно появилось в удачном месте на перекрестке дорог, шедших параллельно побережью (будущая Домициева Дорога (cat. Via Domícia)) и углублявшихся в сторону Атлантики; в III и II вв. до н. э. поселение пережило свой расцвет, наступивший благодаря торговле оловом, доставляемым с Британских Островов.
На этом же месте в 118 году римляне основали свою первую колонию за пределами Италии и назвали ее Narbo Martius; со временем город стал столицей римской провинции Нарбонская Галлия (lat. Gallia Narbonensis). В 45 году до н.э. Юлий Цезарь (cat. Juli Cèsar) разместил здесь ветеранов Х Легиона. В I в. н.э. город достиг максимального расцвета, благодаря оживленному речному порту (в те времена река Од (cat. Aude) протекала через Нарбон более-менее по тому же руслу, где сегодня проходит канал Робин (cat. canal de la Robina)); отсюда контролировались причалы в недалекой лагуне, откуда расходились товары, в первую очередь керамика из Грофесенки (fr. Graufesenque) близ Мийо (cat. Millau) (который тогда назывался Кондутомагус). Золотому веку настал конец, когда город был разрушен сильнейшим пожаром в 145 году, но и после этого он продержался до IV века.
От римского периода до нас дошло мало материальных памятников: прежде всего это фрагмент Домициевой Дороги, недавно обнаруженный под ратушной площадью Отель-де-Виль (cat. plaça de la Vila), и Орреум (lat. Horreum) (подземные зернохранилища и склады). Также были обнаружены и частично раскопаны храм и амфитеатр, кроме того, известно, что в городе существовали термы и театр. Небольшое количество памятников компенсируется обилием надписей, которые были обнаружены среди материала, использованного на исходе эпохи античности для строительства городских стен, разобранных в 1869 году.
В 462 году в земли Нарбона пришли вестготы, при которых город стал столицей Септимании (cat. Septimània) вплоть до арабского завоевания. Первый раз арабы заняли Нарбон в 715 году, затем город отбили, но в 719, при Аль-Самхе ибн-Малике аль-Хавлани (cat. Ass-Samh ibn Màlik al Khawlaní), город опять пал, и при арабах назывался «Арбун» (cat. Arbuna). В 734 герцог Прованса Мавронтиус (cat. duc de Provença de nom Mauront (Maurontus)) подписал договор с вали Юсуфом ибн Абд ар-Рахманом аль-Фихри (cat. Yússuf ibn Abd-ar-Rahman), который позволил ему занять некоторые города в долине Роны (cat. Roine), чтобы защитить Прованс от нападений Карла Мартелла (cat. Carles Martell) и раздвинуть границы своего герцогства к северу. В 737 году Карл Мартелл ответил на это, захватив Авиньон (cat. Avinyó) и напав на Арбун; атака была отбита, несмотря на победу, одержанную Карлом Мартеллом на реке Бер (cat. Batalla de la Berre).
В 752 году город осадил король франков Пипин Короткий (cat. Pipí el Breu), но также не смог его завоевать, и был вынужден уйти, оставив небольшое и малоэффективное войско под стенами Нарбона. При осаде Нарбонны погиб граф Нима Ансельмунд (cat. comte de Nimes Anselmond) (754 год). В 756 году была предпринята попытка возобновить осаду, но безуспешно. Между 756 и 759 годами франки пытались завладеть городом, который защищали вестготы при тесном содействии мусульман. Король пообещал вестготам, что если Арбуна станет франкской, то он позволит их общине жить по собственным законам и обычаям; в конце концов в 756 году так и произошло, что положило конец трехгодичной осаде Арбуны. Вестготы овладели городом изнутри, перебив немногочисленный сарацинский гарнизон и открыв ворота франкам.
Вслед за Арбуной другие города, которые не сделали этого раньше, также сдались франкам: прежде всего, Каркассон (cat. Carcassona), Лодев (cat. Lodeva) и Эльн (cat. Elna), но первые два, похоэже, ранее находились в руках герцога Аквитании Вайфара (cat. Waifré d’Aquitània). Эльн со всем Руссильоном и Конфланом (cat. Conflent) сдался войскам Пипина вскоре после Нарбона. Король отдал церкви половину города с причитающимися службами внутри и вне стен и половину прав на налоги, которые граф собирал от имени короля со всей епархии; треть подобных прав была пожалована и другим церквям Септимании. В Нарбоне и других городах король поставил своих графов, которые в большинстве случаев были теми же самыми вестготскими вельможами, что занимали подобный пост при мусульманских вали.
Окрестные территории продолжали подвергаться нападениям мусульман, особенно стоит отметить 793 год, когда Абд аль-Малик ибн Абд аль-Вахид ибн Мугхит (cat. Abd-al-Màlik ibn Mughith) подошел к самым стенам города, сжег прилегающие к ним районы и разбил графа-герцога Тулузского (cat. Comte duc de Tolosa) в битве на реке Орбье (cat. Batalla de l’Orbieu) неподалеку от Нарбона, а затем отошел на прежние позиции с богатой добычей. Последний набег, не принесший никаких результатов, произошел в 840 году.
В Средние Века власть в Нарбоне делили архиепископ и виконт. В 1306 году, по приказу французского короля, из города были изгнаны евреи. В 1320 году, из-за разрушения плотины, Нарбон утратил свое положение морского порта. С этих пор и до конца XIV века город понемногу приходил в упадок из-за Столетней Войны (cat. Guerra dels Cent Anys), эпидемии чумы 1348 года и изменения направления торговых операций. После заключения Пиренейского мира (cat. Tractat dels Pirineus) в 1659 году, Нарбон перестает быть пограничным и утрачивает свое военное значение. В качестве города, где находилась кафедра архиепископа, который изначально возглавлял генеральные штаты Лангедока, Нарбон всегда был церковным городом.
В середине XIX века строительство железной дороги и расширение площадей, занятых виноградниками, придали городу новый импульс. В 1871 году в Нарбоне была провозглашена Коммуна (cat. Comuna). Позднее, в 1907 году, в виноделии разразился кризис, и виноделы Лангедока и Руссильона выступили против мэра Эрнеста Феррола (cat. Ernest Ferrol). Роман Жоана-Даниэля Безсонова (cat. Joan-Daniel Bezsonoff) «Восстание горбунов» (cat. La revolta dels geperuts) (1998) посвящен именно этим событиям.
