V 5. stoletju pr. n. št. sta ozemlje Belluna naseljevali ljudstvi Venetov in Keltov. Samo mesto je bilo ustanovljeno okoli leta 220–200 pr. n. št. kot romansko - keltski Belodunum. Leta 181 pr. n. št. je postal pomembno središče rimske vojske. Po padcu Zahodnorimskega cesarstva so nadzor nad njim vzpostavili Langobardi (6. stoletje), kasneje karolingi (8. stoletje). Od poznega 9. stoletja je bil pod vladavino knezoškofa, ko je dobil grad in mestno obzidje. Leta 1404 se je po dolgem tekmovanju za ozemlje s Trevisom predal Beneški republiki. Od takrat naprej je bilo mesto pomembno središče za splavljenje lesa iz doline Cadore po reki Piavi. Po padcu Republike je Belluno postal del Avstrijskega cesarstva, dokler ni bil leta 1861 priključen Kraljevini Italiji.