графа Миниха к организации поселенных войск был не случаен. Значительная часть его военной карьеры прошла под началом принца Евгения Савойского – создателя полков «военной границы» в австрийской имперской армии. Познания в обустройстве «Grenzregimenter» он постарался применить и на российской службе.
Работы по возведению Украинской укреплённой линии начались весной 1730 года и шли под общим командованием Миниха. Непосредственно же руководил работами Киевский генерал-губернатор, граф Вейсбах, а организовывали их генералы Андрей Дебриньи и Алексей Тараканов.
До конца октября того же года было построено 10 крепостей (из намеченных 16). В основном они возводились в виде бастионных четырехугольников. В каждой из них строились казармы, цейхгауз, пороховой погреб, казна, колодец. Крепости были соединены непрерывным валом и рвом, протяжённостью около 300 км. Межкрепостные пространства были усилены редутами, частоколом, блокгаузами, форпостами.
Первая из заложенных крепостей получила название Ивановская (Святого Иоанна) «во имя блаженныя памяти Великого Государя Царя и Великого Князя Иоанна Алексеевича…». Позднее, в честь матери императрицы Парасковьи Фёдоровны была заложена Парасковейская крепость (ныне – село Парасковия Харьковской области). В честь первых царей из династии Романовых была названы Михайловская и Алексеевская крепости (ныне – сёла Михайловка и Алексеевка Первомайского района Харьковской области). Именем небесного покровителя Петра I была названа Петровская крепость (ныне – село Петровское Харьковской области).
Строительные работы в основном проводились силами казаков малороссийских и слободских полков, а также крестьян, принадлежавших казацкой старшине, духовенству и помещикам (около 30 тыс. человек ежегодно).
Возводить оборонительные сооружения приходилось в экстремальных условиях, т. к. Крымское ханство пыталось помешать строителям частыми и жестокими набегами. Сказывалась нехватка воды, строительных материалов. Вследствие большой спешки и непрофессионализма строителей качество возводимых сооружений сильно страдало. Поэтому уже в 1734 году Военная коллегия постановила провести переделку и починку «худых мест» линии.
Участие в строительных работах принимали и солдаты ландмилиции. В январе 1731 года специальной инструкцией было установлено, что службу на укреплённой линии следует нести 16-ти конным и 4-м пешим полкам.
Новые полки ландмилиции формировались за счёт однодворцев Белгородской и Воронежской губерний. Ещё со времени становления Российского государства эти южные регионы заселялись служилыми людьми. За ними закреплялись поместья и оклады, за которые они несли военную службу, защищая от неприятельских нападений «тамошние пограничные места яко свои жилища».
Правительство предписало размещать поселения русских однодворцев вдоль Украинской линии, отвести им землю и другие угодья, «каждому столько же, сколько
