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

И вот по воле императрицы Мельгунову вновь предстояло заняться расследованием злоупотреблений в Новой Сербии. Но на этот раз исходя из государственных интересов.

Комиссией Мельгунова был составлен проект преобразований пограничных провинций на юге, который был утверждён императрицей в начале 1764 г. Ведомственная разобщённость и бесконтрольность местных чиновников ликвидировалась. Учреждалась Новороссийская губерния, первым губернатором которой стал всё тот же Мельгунов. Национально-территориальные образования в Новороссии упразднялись. Вместо них вводились 3 провинции: Елисаветинская, Екатерининская и Бахмутская.

Вся земля бывшей Новой Сербии (1421 тыс. десятин) была разделена на участки в 26 десятин (на земле с лесом) и 30 десятин (на безлесной земле). Получить землю в наследственное владение могли «всякого звания люди» при условии поступления их на военную службу или записи в крестьянское сословие. Земельные участки приписывались к восьми местным полкам: Чёрному и Жёлтому гусарским, Елисаветградскому пикинёрному (на правобережье Днепра), Бахмутскому и Самарскому гусарским, а также Днепровскому, Луганскому, Донецкому пикинёрным полкам (на левобережье Днепра). Позднее на основе этого полкового деления ввели уездное устройство.

В 60-е годы XVIII века началось заселение Новороссийской губернии за счёт внутрироссийских переселенцев. Важную роль сыграла отмена запрета на поселение в Новороссии для жителей Левобережной Украины. Миграции крестьян из центральных губерний России способствовала раздача земель военным и гражданским чиновникам – дворянам. Для обустройства вновь полученных владений они стали перевозить на юг своих крепостных.

В 1763–1764 годах были изданы специальные законы, регулировавшие положение иностранных переселенцев. Они получили разрешение селиться в городах или сельских местностях, индивидуально или колониями. Им дозволялось заводить мануфактуры, фабрики и заводы, для чего они могли покупать крепостных крестьян. Колонисты имели право открывать торги и ярмарки без обложения пошлинами. Ко всему этому добавлялись различные ссуды, льготы и иные поощрения. Была специально учреждена канцелярия опекунства иностранцев.

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

Тем не менее, в этот период формировались условия для преимущественно русско-украинской колонизации Новороссии. Результатом данной политики явился стремительный рост населения в южных пределах Европейской России. Уже в 1768 году без учёта регулярных войск, находящихся в регионе, в Новороссийском крае проживало около 100 тыс. человек.

На протяжении года (до марта 1764 года) административным центром Новороссийской губернии являлась крепость Святой Елизаветы (ныне город Кропивницкий). Мельгунов активно трудился над приданием ей облика города. Губернатор озаботился организацией строительства каменных домов, создал первое образовательное учреждение – школу для офицерских детей.