Однако осуществлять подобные реформы было нелегко, поскольку Степан мог рассчитывать лишь на отряд, состоявший из 15 человек, то есть свою личную охрану. Только в конце 1772 года специально для контроля над исполнением судебных приговоров был создан отряд из 80 человек, которым управлял ранее служивший у русских С. Баряктарович. Приговоры выносил суд из 12 человек. Еще одной из заслуг самозванца стала перепись населения, проведением которой занимались пять старшин. Чтобы упрочить свою власть, Степан Малый издал специальную грамоту, провозгласившую отделение церкви от государства.
Черногорцы с одобрением восприняли реформы «царя». А. М. Обресков доносил в Петербург из Константинополя: «Прекратил между славянским народом разных званий издревле бывшие между ними вражды». Савва писал: «Начал между народом черногорским великое благополучие чинить и такой мир и согласие, что у нас еще никогда не было».
Степану удалось добиться резкого сокращения кровавых распрей и установить порядок на дорогах в условиях борьбы с венецианцами и турками. Авторитет его возрос до такой степени, что о нем даже слагали легенды. Одна из них рассказывает о том, как Степан рассыпал на дороге золотые монеты и положил пистолет в серебряной оправе. Все эти вещи оставались нетронутыми в течение нескольких месяцев.
Из многих мест Степан получал письма с заверениями, что народ «готов пролить кровь за царскую славу». Некоторые албанские села отказались платить харач туркам. Поддерживали самозванца и на Адриатическом побережье. Один из почитателей государя сложил в честь Степана сонет, в котором были такие слова: «Спустя пять лет после того, как ужасным образом сорвана корона с чела, приходит беспокойная тень в эти горы, чтобы найти здесь благочестивое успокоение». Далее звучит призыв: «Но если не хочешь отдыха на этой земле, иди туда, роковая тень, где у тебя было отнято царство, и подними войну». В этих строках звучало своеобразное пророчество, предвещавшее крестьянскую войну 1773–1775 годов. В начале 1774 года дубровницкий посланник в Петербурге, Ранина, писал на родину: «В губернии Оренбург, около сибирской границы, восстал один человек, в некотором роде Степан Малый, который выдает себя за Петра Третьего».
Венецианскую республику беспокоила судьба далматинских владений, население которых открыто выступало в поддержку самозванца. Правительство пыталось избежать войны, поэтому венецианский суд инквизиторов отправил которскому проведитору предписание «прекратить жизнь иностранца, виновника происходящих в Черногории волнений», к посланию прилагались несколько флаконов с ядом и отравленный шоколад. Исполнителю сего предписания заранее было обещано помилование, убежище в Венеции и денежное вознаграждение в 200 дукатов. Однако нанятые венецианцами люди не смогли пробраться к Степану, так как охрана ни на минуту не оставляла его. Степан же стремился решить конфликт мирным путем и отправил в сенат письмо: «Вижу, что готовите войска для того, чтобы опустошить три общины (Маине, Побори и Браичи, перешедшие на сторону Степана), которые никому не причинили зла… Прошу не губить людей ради меня и оставить меня в покое». Но это письмо не привело к желаемому результату.