Er was vermoedelijk al een Gallische nederzetting aanwezig toen de Romeinen de plaats bezetten. De Romeinen noemden de plaats Aballo of Aballone. Deze naam is afkomstig van het Gallische Aballon, dat appelboom betekent. Gelegen langs de heerbaan van Lugdunum (Lyon) naar Gesoriacum (Boulogne) ontwikkelde de plaats zich tot een stadje.
Avallon wordt door sommigen beschouwd als de plek van het legendarische Avalon van koning Arthur. Deze mythische koning zou dan geïdentificeerd moeten worden met Riothamus, een Britse krijgsheer uit de vijfde eeuw die zich uiteindelijk zou hebben teruggetrokken in een stad die Avallon heette.
Al in de achtste eeuw was er een kerk in het castrum van Avallon. Deze kerk ontving rond het jaar 1000 relieken van de heilige Lazarus en werd toen gewijd aan deze heilige. Avallon werd toen een bedevaartplaats voor deze heilige die werd aanroepen tegen de pest. In de negende eeuw werd de plaats voorzien van vestingwerken. Avallon werd een gemeente met schepenen in de dertiende eeuw. Op de Cousin kwamen watermolens en leerlooierijen en op de heuvels rond Avallon lagen wijngaarden. In 1653 kwamen er een college en een kapucijnenklooster in Avallon.
De oppervlakte van Avallon bedroeg op 1 januari 202326,75 vierkante kilometer; de bevolkingsdichtheid was toen 235,7 inwoners per km². De Cousin stroomt door de gemeente.
De onderstaande kaart toont de ligging van Avallon met de belangrijkste infrastructuur en aangrenzende gemeenten.
In het stadje, dat geheel omgeven is door versterkte wallen, bevinden zich enkele historische gebouwen:
de romaansekapittelkerk Saint-Lazare dateert uit het midden van de twaalfde eeuw en heeft twee decoratieve gebeeldhouwde portalen. De voorganger van deze kerk dateerde uit de achtste eeuw.
de Tour de l'Horloge, die 49 meter hoog is, werd gebouwd tussen 1456-1460 en deed dienst als stadhuis tot 1772.
Verder is er het museum Musée de l’Avallonnais, een streekmuseum opgericht in 1862 met onder andere een collectie rond de goudsmid en juwelenmaker Jean Després (1889-1980).
