У давнину на місці майбутньої фортеці Кілія існувала грецька фортеця Ахіллея. Назва, схоже, походить від імені грецького героя Ахілла, похованого, за переказами, в гирлі Дунаю. Назва Кілія, яка вперше згадується в 1281 році арабо-перським літописцем Рашидом Аль-Діном, походить від грецькогоΚελλια, «зерносховища».
Середньовіччя
До X століття фортецею керували візантійці. Пізніше вона перейшла у володіння генуезців. У цей період фортеця називається Лікостома.
Реєстр, який зберігався в Кілії генуезьким нотаріусом Антоніо де Поденцоло в період з листопада 1360 по травень 1361 року, свідчить про інтенсивну комерційну діяльність на Нижньому Дунаї. Звідси велику кількість пшениці, меду, воску, вина, солі, риби та інших продуктів вивозили до Константинополя.
22 липня1462 року воєвода Молдавський Штефан ІІІ Великий взяв в облогу фортецю Кілію, яку захищав угорський королівський гарнізон. Під час нападу Штефан отримав травму щиколотки. За традицією, Штефан Великий програв лише дві битви, однією з яких стала облога Кілії в 1462 році. Через два з половиною роки, 25 січня1465 року, після одноденної облоги (24 січня), Стефан Великий завоював кілійську фортецю. Правитель називає Ісаю, свого швагра, старшиною міста. Для вдосконалення оборонної системи влітку 1479 року Стефан Великий відбудував на лівому березі Дунаю фортецю Кілія. У роботах взяли участь 800 мулярів та 17 000 допоміжних засобів.
У 1484 році відбувся похід султана Баязида II на Молдавію. 6 липня того ж року з військом понад 60 000 осіб починається облога фортеці Кілія, яку захищали 400 молдаван. Через вісім днів, 14 липня, османам вдалося завоювати фортецю.
Фортеця перебуває в стані руїни. Зараз від фортеці, яка знаходиться на приватній території промислового підприємства, залишилася лише вежа (ймовірно, каплиця цитаделі).