С большим успехом удается выполнить другое отцовское поручение. После долгих месяцев настойчивых стараний он получает у королевского архивариуса дона Рамона Сасо-и-Ортеги генеалогию рода Миранда, из которой явствует, что это, пожалуй, самая знатная фамилия во всем испанском королевстве. Оказывается, что среди предков Миранды были храбрые рыцари, покрывшие себя славой в борьбе с маврами, непобедимые военачальники, князья и графы, аббаты, иезуиты и знаменитые богословы, в том числе чуть ли не сам Фома Аквинский и многие другие, имена которых, как скромно пишет летописец, он был вынужден опустить, ибо для описания всех носителей благородной фамилии Миранда потребовался бы солидный том. Летописец указывает далее, что имеются «достаточные основания», дающие право Миранде пользоваться фамильным гербом, на котором изображены пять полуобнаженных торсов девственниц-христианок, освобожденных, согласно «архивным данным», из мавританского плена его предком доном Мелендо Анальсо де Мирандой.

Этот документ в стиле эпохи давал Миранде основание, правда весьма шаткое, пользоваться графским титулом. Не придавая значения дворянским титулам, Миранда пользовался ими только тогда, когда обстоятельства и интересы дела принуждали к этому.

В 1773 году двадцатитрехлетний креол капитан дон Франсиско Миранда начал свою военную службу в пехотном полку имени Принцессы в городе Малаге. Не успел молодой офицер ознакомиться с правилами гарнизонной службы, как вспыхнула война Испании с марокканским султаном Сиди Мухамедом, войска которого осадили крепость Мелилью, захваченную еще в 1493 году испанцами на марокканской территории. В Марокко на помощь осажденным был переброшен полк Принцессы.

В Африке Миранда провел около двух лет. Он участвовал в обороне Мелильи, находился вместе с осажденными в течение многих месяцев под обстрелом марокканской артиллерии, когда по городу было выпущено 8 тысяч снарядов, перенес вместе со всеми голод, эпидемии, страдал от невыносимо палящих лучей африканского солнца.

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

Миранда тяжело переживает этот афронт. Он обращается к начальству с просьбой перевести его в колонии, в Америку. И вновь отказ. Тогда он направляет королю петицию с просьбой разрешить ему перейти на службу во флот. Он сообщает королю, что хорошо знаком с математикой, владеет английским, французским, итальянским, латынью и другими языками. Король приказывает отклонить дерзкую просьбу креола. Миранде не остается другого выхода, как временно смириться, набраться терпения и ждать.

Тем временем его полк возвращается в Испанию. В конце 1775 года Миранда проездом останавливается в Гибралтаре, который Англия захватила у Испании в 1704 году. Губернатор Гибралтара майор Бойд радушно встретил Миранду. Он надеялся узнать от молодого офицера не только подробности осады Мелильи, но кое—что и о его родине — Венесуэле, к которой, как и к другим испанским колониям, английское правительство всегда испытывало острое любопытство. Особенно был заинтересован в беседе с Мирандой молодой английский негоциант Джон Тэрнбулл, друг майора Бойда, прибывший встретить вместе с ним Новый год. Тэрнбулл специализировался на контрабандной торговле именно с Венесуэлой.