Для наказания морских разбойников Перовский снарядил отряд в 550 человек уральских казаков, который, разделившись на две партии, рассеял киргизские скопища и привел в 1837 году в Ново-Александровское укрепление 53 человека пленных; скота было отбито столько, что продажею его покрыты все издержки экспедиции. Затем разослано адаевцам и союзникам их в деле грабежей туркменам объявление, что за каждый будущий разбой последует подобное же наказание. Тогда же по распоряжению Перовского для наказания других хищников были произведены три поиска в степи, первый ― до песков Барсуки; второй ― до реки Хобды и третий ― до песков Тайсуган (последние против Кулагинской крепости на Нижнеуральской линии). С появлением войск в степи хищники везде были рассеяны, вышеозначенные приказчики немедленно отпущены ими на свободу и часть товаров возвращена; сверх того войсками захвачены важнейшие главари хищнических шаек и взято множество голов скота для покрытия экспедиционных издержек.
В 1836 году по распоряжению Перовского устроены в Оренбурге генерал-губернаторский дом (служащий ныне помещением казенной палаты и губернского казначейства) и Караван-Сарай для башкир.
В 1837 году сделано распоряжение о предании военному суду киргиз, изобличенных в измене, убийстве, грабеже, баранте (угоне скота) и неповиновении властям.
В том же 1837 году 12—15 июня проездом из Тобольска Оренбург посетил Наследник Цесаревич, впоследствии Государь Император Александр II.
С 1-го января 1838 года в Оренбургском крае появилась первая официальная газета «Оренбургские губернские ведомости» в Уфе, неофициальная часть которых стала выходить с 1843 года.
В том же 1838 году произошло разграничение киргиз Оренбургского и Сибирского ведомств, причем с киргиз Оренбургского ведомства установлен кибиточный сбор по 1 руб. 50 коп. в год.
В том же 1838 году на Преображенской улице города Оренбурга, близ крепостного вала, устроены Перовским обширные Александровские казармы.
Ему же, Перовскому, Оренбург обязан построением общественного собрания.
За отсутствием почтовых, твердо проложенных дорог, Перовским введена была так называемая «летучка» ― своеобразный род почты. Чрез каждые 25 верст стояло несколько конных башкир. Гонец башкир подлетал с почтовой сумкой, бросал ее следующему очередному башкиру, тот схватывал ее налету и мчался во весь дух, сломя голову, свои 25 верст для того, чтобы перебросить сумку следующему, и т.д. Скорость такой доставки чуть ли не равнялась скорости курьерского поезда.
