Meledunum began as a Gaulish town; Caesar noted Melun as "a town of the Senones, situated on an island in the Seine"; at the island there was a wooden bridge, which his men repaired. Roman Meledunum was a mutatio where fresh horses were kept available for official couriers on the Roman road south-southeast of Paris, where it forded the Seine.

The Normans sacked it in 845. The castle of Melun became a royal residence of the Capetian kings. Hugh Capet (See also: House of Capet) gave Melun to Bouchard, his favorite. In the reign of Hugh's son, Robert II of France, Eudes, the count of Champagne, bought the city, and the king took it back for the viscount in 999. Le Chatelain and his wife, who had sold the city, were hanged. Robert died there in July 1031.

The early viscounts of Melun were listed by seventeenth- and eighteenth-century genealogists, notably Père Anselme.