Пока все это происходило, Гладкий не терял времени и разъезжал по разным местам, отыскивая удобные земли под поселение войска. Как видно из рапорта его от 19 декабря 1830 года, он побывал в Мариуполе, в Таганроге и Одессе, издержал, кроме полученных от казны денег, еще своих 647 р. на прогоны «при осмотре земель к поселению запорожцев». Поездки эти казачий атаман совершал по личному распоряжению графа Воронцова, и его поиски свободных земель увенчались успехом. В Мариупольском округе оказалась Бердянская пустошь в 43 141 дес., удобная для поселения на ней запорожцев. Гладкий составил по этому поводу записку, в которой просил поселить на отысканной им земле запорожцев, даровавши им ряд льгот, и в том числе право свободной продажи вина. Воронцов признал все льготы, испрашиваемые Гладким для войска, полезными, но вольную продажу вина находил неподходящей для казаков. Взамен того он предполагал отдавать в откуп виноторговлю на землях Дунайского полка, а получаемые с откупа деньги отдавать, по расчету на каждое селение войска, «в общественный запорожцев доход».
Все это были, так сказать, только предварительные соображения о будощности войска, которое, зимуя в чужом краю, находилось в неопределенном положении. Гладкий тем не менее зорко следил за интересами своего полка и в тех случаях, когда они нарушались, энергично отстаивал их. Когда Херсонское рекрутское присутствие отдало в солдаты запорожца Пономаренка, бывшего раньше мещанином г. Бериславля, Гладкий потребовал немедленного возвращения его в войско. Иронизируя на счет «дружеского соглашения херсонского рекрутского присутствия с бериславскими мещанами», пожелавшими отправить запорожца в солдаты, в зачет своих рекрутов, он удивлялся, как это местные начальники не знали, что Пономаренко запорожец, когда сам Гладкий известил их об этом. Основываясь на том, что все запорожцы, бежавшие в Турцию, прощены были Государем, Гладкий требовал, чтобы «воля Государя не переменялась» чиновниками.
Прошло несколько месяцев. Пономаренко не был возращен в войско. В марте 1831 года Гладкий вновь напомнил новороссийскому и таврическому генерал-губернатору о случае с запорожцем Пономаренко. Под влиянием этого случая, писал казачий полковник, запорожцы снова начали убегать в Турцию, опасаясь, как бы и им не выпала участь Пономаренка. Побеги могли участиться именно благодаря наглядному примеру бесцеремонного обращения с казаками Дунайского полка. В мае того же года Гладкий жаловался графу Палену, исполнявшему обязанности генерал-губернатора, что его предместник по замещению генерал-губернаторской должности не ответил даже на его представления по этому предмету, сделанные пять месяцев тому назад. Неправильно взятый в рекруты запорожец Пономаренко оставался в солдатах. Другой запорожец, Чалый, прослуживший 30 лет в войске, был взят и отправлен против его желания на родину для водворения. Гладкий просил ускорить движение обоих дел и добился впоследствии возвращения в войско Чалого и Пономаренка. Когда Чалый, взявший в Киевской губернии свидетельство на три месяца, явился в войско, то Гладкий, оставивши его у себя, сообщил об этом генерал-губернатору и просил его взыскать с херсонского губернского правления за убытки, причиненные Чалому, по 2 рубля ассигнациями в день, как суточный его заработок, за все время с 28 октября 1830 года по 18 марта 1831 года. Пономаренко же был возвращен на счет виновных.
В «докладной записке полковника Гладкого о водворении запорожских казаков при Мариуполе», помеченной 21 декабря 1831 года, бывший кошевой Турецкой Запорожской Сечи подробно изложил те условия, которые были необходимы, по его мнению, для существования предводимых им запорожских казаков.
По мнению Гладкого, запорожцам следовало отдать под поселение всю Бердянскую пустошь, по расчету на 1648 душ муж. пола. Но одной Бердянской пустоши было недостаточно для казаков. Ее не хватало на наделение землей 17 казачьих обер-офицеров, и, кроме того, в войско могли явиться из Константинополя новые запорожцы. Нужно было обеспечить землей тех и других.
Так как на всей Бердянской пустоши было только два, «с текучей водой и рудниками удобных мест» под селения, то запорожцам следовало отдать 4 из 12 дес. земли, предназначенной для селения израильских христиан и примыкавшей к границе Бердянской пустоши.
На сооружение церкви, постройку домов, покупку волов, возов, плугов и пр. Гладкий просил выдать из казны 81 260 р.
Войску должны быть предоставлены — или вольная продажа вина, или соответственные поступления в пользу казаков от откупной продажи вина.
Для вырубки сох, перекладин и хвороста на строения войску следовало разрешить в течение трех лет свободный въезд в казенные леса Бахмутского уезда.
Безусловно, необходимо также разрешить казакам постройку рыболовных изб и сараев на берегу Азовского моря, между рекой Бердой и землями Мариупольских греков, и ловить беспошлинно рыбу.
Для нужд семьи и хозяйства требовался беспошлинный отпуск соли из Крымских соляных озер или из Черномории по три пуда на душу.