Navnet Hindsgavl nævnes første gang i Kong Valdemars Jordebog fra 1231, hvor en middelalderlig borg formodes at have ligget. I 1295 omtales stedet direkte, da kong Erik Menved på Hindsgavl indgik en våbenstilstand med den norske konge Erik Magnusson Præstehader.
Nordvest for det nuværende Hindsgavl findes resterne af den gamle borg tæt ved kysten. Anlægget består af en ca. 15 meter høj, oval borgbanke med et plateau på omkring 85 x 70 meter. En del af vestskrænten er i dag borteroderet af Lillebælt, mens de øvrige sider er omgivet af en 5–8 meter bred, vandfyldt voldgrav.
Den omgivende eng, som tidligere var sumpet, gav naturlig beskyttelse mod angreb. Adgangen skete via en vejdæmning fra øst, der førte til borgens ladegård på en lav forhøjning syd for banken. Herfra førte en vindebro og en vej op til borgens top, hvor man stadig kan se rester af fundamenter fra de middelalderlige bygninger.
