Le nom et la localisation suggèrent une implantation à l'époque romaine. La première mention dans les textes remonte au 13e siècle. Courtépée précise qu'Heuilley était une annexe de la paroisse de Maxilly-sur-Saône, qu'"il y avait jadis un port sur la Saône où il se faisait plus de chargements qu'à présent. [...] les maisons sont couvertes en paille [...]. L'île de Fley, formée par la Saône, à un quart de lieue, est aux habitants, qui y jouissent de 100 journaux de près, et en ont cédé à la paroisse de Brois [sic] en Comté, 20 journaux par accord en 1772."

Un plan daté vers 1785 (AD21) indique le hameau "Maisons d'Euïlley" le long d'un bras mort de la Saône. Une dizaine de constructions entourées de haies et de jardin s'égrainent sur un chemin longeant ce bras. Dumorey précise que le port d'Heuilley se trouvait un peu au-dessous de l'île d'Heuilley et qu'il s'y chargeait des grains et du fourrage. Enfin, le cadastre napoléonien de 1825 montre que le village était implanté le long d'un "Lac" (ancien bras de la Saône ?), aujourd'hui disparu et plusieurs rues conduisaient à ce bras, également mentionné par Dumorey.

Par ailleurs, les archives nous apprennent qu'un litige entre l’État et la commune a eu lieu au début du 19e siècle (1815-1838) au sujet de la revendication d'un bras délaissé de la Saône. Ce litige, résultant de la construction d'une redoute en bordure de Saône, a conduit à modifier la géographie des lieux : la presqu'île de Fley est devenue une île et l'embouchure de l'Ognon a été déplacée.