Является преемником старой Полианийско-Килкисской епархии, которая в османское время охватывала Дойранскую казу без северных её частей — наместничество с центром в Дойране, восточной части Гевгелийской казы — наместничество с центром в Гевгелии, Килкисская каза — наместничество с центром в Килкисе и несколько деревень Солунской казы между Вардаром и Галикосом. Епископ Дойранский подчинялся архиепископу Фессалоникийскому.
Титул правящего архиерея был Поленинский и Вардарский ( или или или ), но со временем «Вардарский» отпало.
В 1913 году епархия была разделена между Грецией и Сербией. В связи с этим резиденция епископа из Палеа-Дорани (ныне Дойран, Северная Македония) переместилась в Килкис. Часть, оставшаяся в Сербии, сегодня является частью Струмишской епархии Македонской православной церкви. Остальная часть становится Полианийской и Килкисийской епархией с центром в Килкисе. В октябре 1924 года указом патриарха Константинопольского Григория III епархия получила статус митрополии. В епархию входила территория всего нома Килкис и несколько сёл нома Салоники.