Первая из заложенных крепостей получила название Ивановская (Святого Иоанна) «во имя блаженныя памяти Великого Государя Царя и Великого Князя Иоанна Алексеевича…». Позднее, в честь матери императрицы Парасковьи Фёдоровны была заложена Парасковейская крепость (ныне – село Парасковия Харьковской области). В честь первых царей из династии Романовых была названы Михайловская и Алексеевская крепости (ныне – сёла Михайловка и Алексеевка Первомайского района Харьковской области). Именем небесного покровителя Петра I была названа Петровская крепость (ныне – село Петровское Харьковской области).

Строительные работы в основном проводились силами казаков малороссийских и слободских полков, а также крестьян, принадлежавших казацкой старшине, духовенству и помещикам (около 30 тыс. человек ежегодно).

Возводить оборонительные сооружения приходилось в экстремальных условиях, т. к. Крымское ханство пыталось помешать строителям частыми и жестокими набегами. Сказывалась нехватка воды, строительных материалов. Вследствие большой спешки и непрофессионализма строителей качество возводимых сооружений сильно страдало. Поэтому уже в 1734 году Военная коллегия постановила провести переделку и починку «худых мест» линии.

Участие в строительных работах принимали и солдаты ландмилиции. В январе 1731 года специальной инструкцией было установлено, что службу на укреплённой линии следует нести 16-ти конным и 4-м пешим полкам.

Новые полки ландмилиции формировались за счёт однодворцев Белгородской и Воронежской губерний. Ещё со времени становления Российского государства эти южные регионы заселялись служилыми людьми. За ними закреплялись поместья и оклады, за которые они несли военную службу, защищая от неприятельских нападений «тамошние пограничные места яко свои жилища».

Правительство предписало размещать поселения русских однодворцев вдоль Украинской линии, отвести им землю и другие угодья, «каждому столько же, сколько они держали раньше и были бы способны обеспечить себя и могли бы охранять границу так, как охраняли её их деды и прадеды». Кроме того, стражи укреплённой линии получали жалование и налоговые льготы.

Однодворцы направлялись в полки на основе добровольной записи, жеребьёвки или очередности несения службы. Каждый милиционер имел подпомощника, помогавшего в ведении хозяйства и также получавшего государственное жалование. Подпомощников рекомендовалось набирать из числа родственников милиционеров, существовала возможность обмена ролями между ними. В 1733–1742 годах для выполнения функций подпомощников на Украинскую линию ежегодно отправляли более чем 12 тыс. человек.

Содержание ландмилиции обходилось Российскому государству в 500 тыс. рублей в год. В основном эти средства собирались за счёт налоговых платежей всё тех же однодворцев (оставшихся жить в родных местах), плативших специальный семигривенный сбор.

К концу 1732 года полки были официально названы в честь городов, где они в основном формировались: Рыльский, Путивльский, Курский, Севский, Белгородский, Брянский, Старооскольский, Валуйский, Новооскольский, Ливенский, Елецкий, Воронежский, Орловский, Козловский, Тамбовский, Ефремовский, Ряжский, Борисоглебский, Слободской, Белёвский. Это помогает определить географию происхождения первых жителей Украинской линии.

В 1738 году названия ряда полков были даны нескольким новым крепостям между Днепром и Северским Донцом. Так здесь появилась Белёвская крепость (административный центр линии, позже – местечко Белёв, переименованое в Константиноград, а затем Красноград), Ливенская крепость (ныне – село Ливны Полтавской области), Ряжская крепость (ныне – село Рясское Полтавской области), Ефремовская крепость (ныне – село Ефремовка Харьковской области) и др.