Havneby har gennem århundrede blevet brugt som naturlig havn. Stedet var ofte isfrit om vinteren og havde nem adgang til Listerdyb og derfra videre ud i Nordsøen.

Den første plan om at bygge en havn i Havneby blev fremsat så tidligt som i 1858. Krigen i 1864 skrinlagde dog alle planer. Dog foreslog en ingeniør Hübbe fra Slesvig i 1867 at der skulle opføres en verdenshavn som skulle tage konkurrence op med de store havne i f.eks Bremen og Hamborg.

Med først i 1950‘erne blev kom der for alvor gang i tankerne igen og i 1960 vedtog Folketinget loven om anlæg af statshavnen. Havnen stod færdig i 1964.