Новым и весьма авторитетным сторонником Степана в эти месяцы становится сербский патриарх Василий Бркич, изгнанный из своей резиденции в городе Печ после ликвидации турками самостоятельной сербской церкви. В марте 1768 г. Василий призвал все православное население почитать Степана как русского царя. По-видимому, для подкрепления этой версии Степан предпринял эффектный шаг – по случаю дня Петра и Павла, отмечаемых православной церковью 29 июля, он организовал торжественную церемонию в честь Петра Великого, а также цесаревича Павла Петровича как своего сына.

Летом 1768 г. Екатерина отправила в Черногорию советника русского посольства в Вене Г. А. Мерка с «увещевательной грамотой» к тамошним жителям, чтобы не верили самозванцу. Мерк прислал донесение, датированное 9 августа, что ехать на Черную Гору, не подвергая себя смерти, никак не мог, ибо черногорцы необыкновенно привязаны к Малому. Екатерина написала на этом донесении: «Если б капитан гвардии был послан с грамотою к черногорцам, то бы письмо несумненно отдано было; но сей претонский политик возвратился с ней, не сделав, окроме преострые размышления».

Осенью 1768 г. турецкие отряды вторглись в Черногорию, а с севера напали венецианцы. Борьбу с турками возглавил Степан Малый, а с венецианцами – его сподвижник Танович.

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

12 августа 1769 г. на адриатическом берегу Черногории высадился генерал-майор Юрий Владимирович Долгоруков в сопровождении 26 человек конвоя. Ехал он инкогнито, под именем купца Барышникова. Долгоруков поднялся в горы, где был встречен духовенством у монастыря Брчели. Через несколько дней в Цетинье собралась скупщина. В присутствии двух тысяч черногорцев, старейшин и церковных властей Долгоруков обвинил Степана Малого в самозванстве, огласил манифест от 19 января 1769 г. и потребовал от присутствовавших принести присягу на верность Екатерине II, что и было сделано. Долгорукова поддержал сербский патриарх Василий, объявивший Степана Малого «возмутителем покоя и злодеем нации».

Все это происходило в отсутствии Степана Малого. Долгоруков первый раз увидел Малого, когда находился в монастыре Брчели. Тот приехал к нему верхом с конвоем из нескольких черногорцев. Генерал писал: «Разговоры его, поступки и обращения заставили заключить о нем, что он в лице вздорного комедианта представлял ветреного или совсем сумасбродного бродягу. Росту он среднего, лицом бел и гладок, волоса светло-черные, кудрявые, зачесаны назад, лет тридцати пяти, одет в шелковое белой тафты платье, длинное по примеру греческого, на голове скуфья красного сукна, с левого плеча лежит тонкая позолоченная цепь, а на ней под правою рукою висит икона в шитом футляре величиною с русский рубль… Разговоры имел темные и ветреные, из которых, кроме пустоши, ничего заключить неможно, хотя черногорцы и почитают его за пророческое красноречие со страхом и покорностию».

Долгоруков приказал арестовать Малого, но вскоре понял, что без Степана порядка в Черногории не будет, и был вынужден отпустить его. Мало того, Долгоруков распорядился доставить Малому боеприпасы, взял с него клятву в верности России и надел на него мундир русского офицера.