Черногорский монах Софроний Плевкович, приехавший в Киев, рассказывал, что Степан в Майне жил у Марко Вуковича сначала как юродивый, а потом открылся ему, что он Петр III, но не хочет называться этим именем, а будет называться Степаном Малым. Марко, услыхав это, пал пред ним на колена и целовал ему ноги; после этого Степан призвал митрополита и старшин и также объявил себя Петром III, прибавив, что если они не будут его слушаться, то прекращено будет им денежное пособие, идущее из России. Софроний рассказывал, что Малый начал устраивать регулярное войско, обучил его военным упражнениям. Он призвал к себе его, Софрония, и просил идти к императору Иосифу в Вену, и когда Софроний спросил, кто он таков, то Степан отвечал: «На что тебе испытывать такую великую тайну, будь доволен тем, что ты слышишь, что я Степан Малый; я послан ни от цесаря, ни от царя, но от самого Господа Бога Саваофа для спасения рода христианского, потому что уже девять лет, как турки моим хлебом питаются». Софроний должен был просить в Вене военных кораблей и войска. В Глаце Софрония задержали, допросили и объявили ему, чтоб ехал назад, император войска на помощь Малому послать не может. Не смея пробираться по турецким владениям, Софроний поехал в Россию. Относительно наружности самозванца Софроний к приведенному выше описанию прибавил: нижняя губа толстая и отвислая, усы черные, небольшие, волосы темно-русые, побит несколько оспою, весь лоб обвязан полотном, чтоб закрыть две большие жилы. По свидетельству Софрония, Малый знал много языков кроме сербского: итальянский, турецкий, немецкий, французский, английский, греческий и несколько арабский. Императрица по поводу Степана Малого писала графу Алексею Орлову: «Ген. – майор Подгоричани подозревает не без основания, что Степан Малый тот самый итальянец Вандини, который в канцелярии опекунства здесь дело имел и, обманув здесь, выманя алмазы у греческого купца и заложа оные, денег взял и сам ускакал. Подгоричани говорит, что описание фигуры и лица одного и другого совсем сходны, а только Вандини не был ряб, а другой ряб, и с Подгоричаниным писано, что, приехав в Черногорию, Степан в оспе лежал и так ряб ныне, хотя в Петербурге не был таков».
Сначала Софронием хотели воспользоваться, отправить его на Черную Гору, чтоб он поднимал тамошних жителей вместе со Степаном Малым против турок, уговоривши Степана бросить самозванство. Уже написана была инструкция Софронию; но потом передумали, и на инструкции находим надпись, что она не состоялась. Софроний отправился на флоте с адмиралом Спиридовым. Граф Алексей Орлов писал императрице, что он не может одобрить выбора лиц, отправленных для поднятия турецких христиан; Екатерина отвечала ему: «Весьма надежна, что все сделается по желаниям нашим и прославимся в сей век, спасая многие тысячи под варварским игом страдающих единоверных наших. Что же все сие не так скоро исполниться может, как ваше и мое желание бы было, то сие не диво, но в естестве сего великого затея, и весьма похваляю вас, что вы начали так, как ко мне пишете. Что же вы не хвалите тех, кои отселе разосланы были, то в оправдание сего ныне некоторым образом неосторожного поступка я вам скажу, что почти с самого начала войны, когда граф Григорий Григорьевич подал проекты о посылании флота в Средиземное море, думано было, как бы тех народов, с кем вы теперь порядком дело имеете, склонить и приготовить в нашу сторону; с черногорцами же Иностранная коллегия почиталась в ссоре. Признаться же должно, что в самое то время множество греков, сербин и прочие единоверные авантурьеры начали соваться ко многим с планами, с проектами, с переговорами, и между ними, так сказать, брошенный подполковник Эздемирович по чину, по летам и по тому, что он уже заслугу ту имел перед собою, что в прежнее время несколько сот разных народов вывез на поселение в Новороссию, казался лучшим; и как вступили с ним в разговоры и переговоры, и наскакал Ефим Белич, и стал с ним на одной квартире, и, по сказкам Эздемировича, ему открылся, что он прислан от Степана Малого. Сей от нас писанным к черногорцам в прошлых летах публичным манифестом объявлен обманщиком; но как его описывали там весьма сильным, то вздумали его (Белича) употребить, запретя ему обман; с тем и Эздемирович, и Белич, не имев кого лучше, и отправлены были; я думаю, что и грек Петушин в подобном казусе, то есть лучше его не нашли».
Софрония не отправили в Черногорию, боясь, как видно, увеличить им число «авантурьеров». Но и выбор Иностранной коллегии оказался неудачным. Еще летом 1768 года отправлен был советник русского посольства в Вене Мерк на Черную Гору с увещательною грамотою к тамошним жителям, чтоб не верили самозванцу. От 9 августа Мерк прислал донесение, что ехать на Черную Гору, не подвергая себя смерти, никак не мог, ибо черногорцы необыкновенно привязаны к Малому. Екатерина написала на его донесении: «Если б капитан гвардии был послан с грамотою к черногорцам, то бы письмо несумненно отдано было; но сей претонский политик возвратился с ней, не сделав, окроме преострые размышления; я советую его из Вены отозвать, ибо видно, что он способность великую имеет здесь употребленну быть в важнейших делах, а там на него изойдет лишь лишняя коллегии издержка». На Черную Гору с грамотою, возбуждавшею христиан против турок, с порохом и свинцом отправился генерал-майор кн. Юрий Владимир. Долгорукий под именем купца Барышникова. Но для удобства сношений с Черною Горою нужно было соглашение с Венецианскою республикою. С первого раза казалось, что Венецию, исстари враждебную к Порте, нетрудно привлечь на русскую сторону; но Венеция не была уже прежняя отважная владычица южных морей; это был разлагавшийся труп. Венецианское правительство боялось всякого движения, ибо всякое движение могло болезненно потрясти и даже разрушить дряхлое государственное тело. Венеция боялась всех и всего, боялась Турции, Сардинии, Австрии, теперь сильно боялась России, боялась движения, вносимого последнею в славяно-греческий мир, боялась потому восстания своих славянских и греческих подданных. С 1768 года русским поверенным в делах при Венецианской республике был маркиз Маруцци. Он должен был внушать венецианскому правительству, как ему выгодно вступить в союз с Россиею против общего врага, что все завоевания достанутся Венеции, потому что Россия их не хочет и не может иметь в такой дали. Но Маруцци писал Панину, что венециане страшно боятся турок: все войны с последними были гибельны для республики; Россия далеко, не может подать помощи. Маруцци достиг одного: сенат постановил открыть черногорцам сообщение с морем. Относительно Черной Горы Маруцци писал, что владыка Савва – главный виновник смуты и кредита Степана Малого, который уверяет, что настоящая война России с Портою начата единственно из-за него, что его хотят сделать владетелем страны между Скутари и Рагузою. В сентябре 1769 года Маруцци переслал в Россию известие, что кн. Долгорукий успел проникнуть на Черную Гору, захватил Степана Малого и потребовал от проведитора каттарского позволения провезти самозванца чрез венецианские владения для отсылки в Россию; проведитор обратился к сенату, и тот велел пропустить; при этом Маруцци писал, что венецианское правительство обрадовалось аресту Малого.