Un passage d’eau (bac) existait avant la construction du pont au début du 20e siècle. Les tarifs de bac établis en l’an 12 sont détaillés dans les archives. Un procès-verbal de visite du bac des Maillys dressé le 1er avril 1806 indique que le bac est en mauvais état. (12 S 1 a 39).

En 1845, le commune voisine de Trouhans avait délibéré sur la nécessité de faire construire un pont sur la Saône à hauteur de Mailly-le-Port pour faciliter le commerce avec les communes du Jura et la ville de Dole (V 0 368/3).

L'ouvrage est construit au début du siècle suivant : d'après les cartes postales anciennes, on sait qu'il était composé de quatre arches en arc surbaissé ; les écoinçons étaient percés d'ouvertures surmontées d'arcs outrepassés. Un arrêté préfectoral du 6 novembre 1900 indique les préconisations à respecter pendant la durée de la construction de l'ouvrage. Le rapport de l’ingénieur ordinaire du 25 octobre 1900 précise que les travaux ont été adjugés à l'entrepreneur M. Bouquet (12 S 1 a 39). Le Tableau des rectangles navigables des ponts de la Saône de Gray à Lyon dressé en 1910 (3 S 44) décrit ainsi le pont des Maillys : pont en maçonnerie de 4 arches de 30 m d’ouverture chacune datant de 1903. C'est cette même description que l'on retrouve dans l’État des ouvrages de la navigation (début 20e siècle - 3 S 10) : 4 arches de 29,5 m d'ouverture en arc surbaissé pour le passage du chemin de grande communication n° 16 de Longeault à Dole.

La reconstruction du pont actuel a débuté en 1952.