Осмотрев мечети, храм святой Софии, знаменитую библиотеку Рашид — паши и другие достопримечательности турецкой столицы, Миранда в сентябре 1786 года направился морским путем в Херсон, эти южные ворота екатерининской России. В зеленом портфеле, с которым он никогда не расстается, кроме рекомендательного письма к князю А. И. Вяземскому, у него письма к генералу Ранинскому, австрийскому консулу Розоровичу, голландскому негоцианту ван-Шутерну… На границе Миранда наравне с другими путешественниками был вынужден пройти карантин — долгих сорок дней в полной изоляции. Русские власти пытались обезопасить себя против черной оспы и других заразных болезней, распространенных во владениях Турецкой империи.
9 ноября 1786 года Миранда, наконец, попадает на русскую землю, в Херсон. Все здесь поражает и привлекает его внимание: люди, их обычаи, климат. Миранда быстро установил контакт с губернатором Херсона князем Вяземским, жена которого оказалась испанкой — племянницей (кто бы мог подумать!) генерала О’Рейлли, того самого, который в свое время так настойчиво преследовал Миранду в Испании. Разумеется, она ничего не знала об этом и отнеслась к графу Миранде чрезвычайно дружелюбно, как к «другу» ее дяди. В результате князь Вяземский пригласил знатного путешественника поселиться в его дворце. Он стал запросто бывать у князя Долгорукова, полковника Нехлюдова, коменданта города Корсакова…
Херсон — пограничная крепость. В городе сорок тысяч жителей, из них добрых две трети военные. Миранда проводит свое время в беседах с офицерами местного гарнизона на военные темы. Почему каракасец задерживается в Херсоне? В этом городе он узнает, что южные провинции России собирается посетить Екатерина II. Приезду императрицы предшествует ее могущественный фаворит Григорий Михайлович Потемкин, князь Таврический, умный и энергичный царедворец. Его ожидают в Херсоне, а так как здесь Миранде кров и пища обеспечены во дворце Вяземских, то он принимает решение дожидаться Потемкина у своих гостеприимных хозяев.
28 ноября у Вяземских Миранду знакомят со знаменитым русским полководцем Суворовым, с которым каракасец вступает в оживленную беседу на излюбленную тему — о военном искусстве.
В тот же вечер в город приехал Потемкин, с которым Миранда впервые встречается два дня спустя у тех же Вяземских. Потемкин принял путешественника с подчеркнутым уважением и радушием, сказал ему различные знаки внимания. «Мы встретили в Херсоне одного испано-американца господина Миранду, — писал впоследствии в своих воспоминаниях один из спутников всемогущего вельможи, принц Нассау-Зинген, — незаурядного и остроумного человека, понравившегося Потемкину».
Сближению Миранды с Потемкиным способствовал в немалой степени адъютант последнего, неаполитанец де Рибас, говоривший по — испански, с которым каракасец быстро установил приятельские отношения. Де Рибас оказывал немало услуг Миранде, в том числе одалживал ему деньги. Но, конечно, основной причиной, побудившей екатерининского фаворита обратить внимание на Миранду, было желание получить достоверные сведения об испанских колониях Америки, к северным границам которых вплотную подошли тогда русские зверопромышленники, продвигавшиеся вдоль тихоокеанского побережья Америки.
В 1784 году, за три года до прибытия Миранды в Россию, купец Шелехов основал русское поселение на Острове Кодиак, вблизи Аляски. Шелехов и другие русские купцы готовились пройти дальше на юг, к Калифорнии. Испанцы разгадали эти планы и, в свою очередь, стали продвигаться на север. В 1768–1769 годах направленная из Мексики испанская экспедиция заняла Верхнюю Калифорнию, затем направились далее на север. В 1779 году испанцы достигли 59° северной широты, считая, что все земли к югу от этой линии являются их собственностью.
За всеми этими событиями внимательно следили Екатерина II и Потемкин. В конце 1786 года императрицу посетил компаньон Шелехова купец Голиков, сообщивший ей о деятельности русских купцов в районе Аляски и южнее. Рассказ Голикова произвел столь большое впечатление на Екатерину II, что она отдала приказ снарядить и направить в район Тихого океана отряд военных судов под командованием капитана Муловского «для охраны права нашего на земли, российскими мореплавателями открытые». В состав отряда входили четыре фрегата и одно транспортное судно. Затем весной 1787 года по указанию Екатерины II в подмогу Муловскому были направлены еще три военных корабля. Учитывая, что Испания держала в Тихом океане для охраны своих американских владений всего четыре линейных корабля и четыре фрегата, направленный Екатериной II флот свидетельствовал о серьезных намерениях заставить Испанию уважать права России в этом районе.