В конфликт между Молдовой и Мунтенией за Килию были втянуты политические и военные силы обеих сторон. 22 июля 1462 года Стефан Великий безуспешно осаждает Килийскую крепость, в которой был расположен венгерский гарнизон. Во время атаки Стефан был ранен в лодыжку. Согласно традиции Стефан потерял только два сражения, и одно из них – битва за Килию в 1462 году.

После неудачной попытки завоевать Килию господарь Молдовы Стефан Великий с согласия Польши, которая обещала ему военную помощь в конфликте с тевтонскими рыцарями, подготовил новую атаку.

После замещения Влада Цепеша Раду Красивым (1462 – 1475) венгерский король Матиаш Корвин уступил эту крепость по соглашению с Мехмедом (1444 – 1446, 1451 – 1481), который включил ее в сферу османского влияния.
 Значимость Килии и Аккермана для Османской империи была отмечена неким современником, который приписывал султану такие слова: «До тех пор пока Килия и Аккерман принадлежат валахам, а сербский Белград – венграм, у нас не может быть ни одной победы».

Продолжая политику Александра Доброго (1430 – 1432), Стефан Великий решил вернуть Килию. Об этом писал Григоре Уреке в своей летописи, отметив, что 23 января 1465 Стефан Водэ собрал в стране войско и, желая вернуть крепости, завоеванные язычниками у других господарей, направился к крепости Килия. Рассчитывая на то, что венгерский король не сможет вмешаться в пользу Раду, будучи занят в Боснии с османами, Стефан добрался до крепостных стен 23 января 1465 года и занялся последними приготовлениями.

Ночью удалось проникнуть в крепость через оставленные открытыми ворота, и началась атака, поддержанная мощным обстрелом: «в пятницу утром ударили и начали биться за крепость Килия. И так бились целый день, и бились до вечера. А в субботу крепость сдалась, и Стефан воевод по воле Божией вошел в крепость», – записано в летописи.

В последующие три дня Стефан Великий назначил пыркэлабами (начальниками гарнизона) своего шурина Исайю и Бухтю. Килия имела большое экономическое и политическое значение: ее завоевание привело как к подрыву позиций Венгрии в регионе Нижнего Дуная, так и к потере значительных источников доходов для всех заинтересованных сторон: Валахии, крымских татар, генуэзцев из Каффы и Османской империи. Так турки стали видеть в Молдове соперника в отношении господства в черноморском (понтийском) регионе.

Чтобы добиться прощения султана, Стефан посылает ему дары и, наверное, был согласен с увеличением дани. Все же, господство над этими важными морскими центрами привлекали соседей, перед армиями которых великий господарь выстоял.

Для улучшения защиты крепости, летом 1479 года Стефан Великий перестроил Килию на левом берегу Дуная (крепость Новая Килия). В работах участвовали 800 строителей и 17 000 разнорабочих.