Эта история, не вызвавшая, в отличие от плаваний графа Орлова, большого интереса у историков и романистов, для истории российской разведки так же уникальна. Впервые приказ на похищение или ликвидацию прямо от верховной власти в Петербурге российский разведчик получил не по отношению к эмигранту-самозванцу Тимофею Анкудинову, не к имевшему российское гражданство гетману Мазепе и его соратникам и даже не к беглому сыну русского царя Алексею, а по отношению к монарху иностранного государства. Хотя, как мы помним, польский агент Ивана Грозного Ян Глебович обещал русским попробовать убить своего короля Стефана Батория, но там, видимо, инициатива шла от самого авантюриста поляка. До 1772 года таких акций, понимаемых сегодня как «политический терроризм», российская разведка не планировала, хотя бы в данном случае речь и идет не о законном монархе, а о самозваном. Карла XII Шведского Петр I требовал выдать ему из турецких владений больше для проформы, отдать приказ на ликвидацию своего уважаемого врага, о смерти которого сам позднее плакал навзрыд, Петр не мог. Эта операция против Стефана Малого, весьма спорная в плане законности, даже по меркам XVIII века, также не была осуществлена. Хотя вины Долгорукова в этом нет, он повел себя как настоящий разведчик, руководствуясь исключительно державными интересами России.
Прибыв в Черногорию из итальянской Анконы на нанятом ночью судне греческих контрабандистов и с небольшим отрядом из русских и сербов, Долгоруков через горы с приключениями добрался до столицы этого края Цетинье, где внезапно предстал перед изумленным Стефаном-Петром и разоружил его стражу. При этом Долгоруков проявил себя не столько офицером-диверсантом, сколько хорошим дипломатом-разведчиком: вооруженное сопровождение самозваного монарха намного превосходило отряд Долгорукова, но он сумел словами убедить черногорцев в том, что перед ними самозванец. После чего даже черногорские священники встали на его сторону, и ему осталось разоружить только кучку особо ярых «четников» из приверженцев Стефана, а самого «Петра III» заковать в цепи.
Из дальнейших бесед с монахом-самозванцем и с его окружением Долгоруков понял, что этот «Петр Федорович» не имеет никаких претензий на российский престол, зато настроен явно антитурецки. Долгоруков освободил Стефана Малого, лишь пожурив его за присвоение чужого царского имени, и приказал забыть про Петра III, а затем оставил в качестве союзного России черногорского короля, отряд Долгорукова даже поделился с маленькой черногорской армией оружием и запасами пороха. От имени российской императрицы Долгоруков возвел Стефана в звание русского офицера. Согласно легенде, Стефан Малый был так признателен великодушному и мудрому русскому разведчику, что даже в разговоре открыл ему свое истинное имя (до сих пор достоверно историками не уточненное) и якобы назвал себя сербским крестьянином из Боснии по фамилии Раичевич. На обратном пути на Долгорукова организовали два покушения сторонники «турецкой партии» среди черногорцев, потому ему пришлось даже имитировать собственную смерть и тайно покидать черногорскую землю на очередном корабле греческих полуторговцев и полупиратов. В Петербурге исход черногорской миссии Юрия Долгорукова был оценен очень высоко, а его решение оставить на черногорском троне Стефана Малого было признано оправданным после заявления разведчика, что остальные черногорцы не очень горят желанием воевать с турками, а Стефан «был единственным среди них культурным человеком, который хотя бы понимал Долгорукова».
Алексей Орлов после этого получил указание поддерживать связь с новым союзником России на черногорском троне, с 1770 года из своего штаба при эскадре Спиридова в Средиземном море Орлов не раз посылал к Стефану своего сербского агента Мркоевича с тайными депешами. Хотя уже с конца 1770 года Стефан Малый, ослепший после покушения на него из-за взрыва бочонка с порохом, уже не так рвался быть проводником политики России на Балканах и воевать с турками за славянскую идею. Этот роман российской разведки с самозваным королем, которого до того она сама же собиралась похитить или убить, закончился в октябре 1773 года — Стефан при очередном покушении на него был зарезан турецким разведчиком Класомунией, «секретная дипломатия» с другой стороны тоже не дремала и метода диверсий для себя также не исключала.