В марте 1887 года Ашинов обратился в Священный синод с прошением о посылке духовной миссии в Эфиопию. Ашинов в роли духовного начальника миссии желал бы видеть лицо, ему вполне послушное. Поэтому он предложил петербургскому митрополиту Исидору поставить во главе миссии своего старинного приятеля Паисия, состоявшего ключником при православном Пантелеймоновском подворье в предместье Константинополя. Правда, будущий глава духовной миссии был неграмотен и едва мог написать свое имя. Но Ашинова это не смущало, скорее было даже на руку — ничего лишнего не напишет. Однако митрополиту этот выбор показался странным, и он вызвал Паисия в Петербург на собеседование. Благообразный и бесхитростный Паисий произвел на Исидора благоприятное впечатление, и назначение последовало. Духовный сан Паисия — инок — для такого серьезного миссионерского дела оказался слишком мал. Положение решили исправить: 6 августа 1888 года Паисий был рукоположен Исидором в иеродиаконы, 7 августа — в иеромонахи, а 13 — в архимандриты. Немногим монахам удавалось делать столь быструю карьеру. Итак, первый успех был Ашиновым достигнут. Вместе с вполне преданным ему главой будущей духовной миссии Ашинов получил возможность легального сбора пожертвований на миссионерское дело. Сбор пошел споро. Бедствия абиссинских братьев по вере, терпящих от происков католиков, не оставляли русских жертвователей безразличными.

Убедить гражданских чиновников оказалось сложнее. Для успеха плана Ашинову требовалась поддержка Военного и Морского министерств. Военное министерство проект Ашинова о привлечении в союзники абиссинцев не вдохновил. Генерала, к примеру Обручева, изумила просьба атамана отпустить тридцать тысяч винтовок Бердана с миллионом патронов для вооружения абиссинской армии. Управляющий Морским ведомством адмирал Шестаков тоже не хотел воспринимать вольного казака всерьез и долго отказывался встретиться с ним. Однако летом 1887 года их знакомство в конце концов состоялось. Ашинов сумел нащупать чувствительные струнки адмирала: их сблизила общая нелюбовь к англичанам. Кроме того, в некотором содействии проекту Ашинова Шестаков увидел возможность решить ряд задач, стоявших перед его собственным ведомством. «А не поздоровится Джону Булю, коли там и сям крейсерам можно будет запасаться углем», — записал он в дневнике после встречи с Ашиновым.

В октябре 1888 года Шестаков и Ашинов договорились о том, что духовная миссия с Паисием и казачья сотня, сопровождающая ее для охраны, будут доставлены на таджурское побережье бесплатно, на пароходе добровольного флота «Россия», капитану которого адмирал дал отдельное задание — осмотреть бухту у ашиновской станицы и оценить ее пригодность для стоянки и бункеровки судов.

К осени 1888 г. все приготовления, по существу, завершились. Было отобрано свыше 150 добровольцев, готовых отправиться в неведомую Эфиопию и ждавших в Одессе погрузки на «Россию». Но внезапно судьба отвернулась от Ашинова. В ноябре 1888 г. адмирал Шестаков скоропостижно скончался. У нового управляющего Морским министерством вице-адмирала Чихачева планы атамана поддержки не встретили, тем паче что в печати появились сведения, опровергавшие заявления Ашинова о якобы основанной им в Африке казачьей станице. Источником этих разоблачений стал некто Степан Самусеев, наемный человек Ашинова. Он был завербован атаманом во вторую поездку в Эфиопию, но, когда эта поездка не состоялась, Ашинов оставил его в числе еще семи человек на берегу Таджурского залива — ожидать возвращения Ашинова с пополнением, охранять оставленное имущество, а заодно олицетворять собой основанное атаманом «поселение».

Прождав несколько месяцев возвращения хозяина, люди мало-помалу стали разбегаться. Двое из них, Самусеев и Шелипенко, добравшись осенью до Константинополя, рассказали в российском посольстве, что Ашинов якобы бросил их без денег и продовольствия на пустынном африканском берегу. Посол Нелидов счел своим долгом сообщить об этом в Петербург.

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

Но Ашинова, вошедшего в азарт и уже видевшего себя новым Ермаком, оказалось не так-то просто остановить. Увидев, что от правительства ждать помощи больше нечего, он полностью взял дело в свои руки, причем столь стремительно, что многие люди, ехавшие с ним с полной уверенностью, будто все предприятие поддерживается государством, даже не успели ничего понять. Ашинов решил во что бы то ни стало выполнить свой план, рассчитывая на то, что победителя, который подарит России африканскую колонию, уж, верно, не осудят. На собранные церковные пожертвования и собственные средства Ашинов купил для всех членов миссии билеты на рейсовый пароход Российского общества пароходства и торговли «Адмирал Корнилов», шедший до Египта, надеясь дальше добраться до места на каком-нибудь попутном судне. Небольшую часть оружия и амуниции, которую он успел получить со складов Морского министерства еще при Шестакове, ему удалось спрятать и перед отплытием тайно погрузить на пароход.

В начале декабря 1888 года «Корнилов» с духовной миссией на борту вышел из Одессы, провожаемый теплыми напутствиями жителей города. Перед отплытием сам контр-адмирал Зеленый, градоначальник Одессы, провел поверку отъезжающих. Ашинову удалось договориться с властями Одессы о том, чтобы члены духовной миссии были выпущены за границу по общему списку, без оформления загранпаспортов — по примеру едущих на российский Дальний Восток. Часть членов миссии значилась богомольцами, следующими к святым местам, часть — переселенцами на Дальний Восток. Если целью Ашинова при этом было не привлекать к своей экспедиции излишнего внимания Министерства иностранных дел, то план его вполне удался. Причем удался настолько, что внешнеполитическое ведомство узнало об отплытии ашиновской миссии лишь из газет. А узнав, сначала не придало этому особого значения. Первыми всполошились итальянцы, не желавшие появления русских в Красноморье: у них были свои цели в Эфиопии.

19 декабря русская духовная миссия прибыла в Порт-Саид, дальше которого рейсовые российские суда не ходили. Почти недельное пребывание ашиновцев в главном пункте Суэцкого канала, где им пришлось ждать попутного парохода, не могло не привлечь к русской миссии внимания европейских держав. Европейские газеты наперебой обсуждали цели миссии и отношение к ней российского правительства. Между тем последнее пребывало в состоянии некоторой растерянности, не успев даже своевременно уведомить об отъезде миссии свои консульские службы на Востоке. Германский консул в Порт-Саиде, выполнявший по совместительству и обязанности российского вице-консула, на основании отсутствия у него инструкций отказал «духовной миссии» в официальном покровительстве.

24 декабря Ашинову наконец удалось посадить миссию на австро-венгерский пароход «Амфитрида», который согласился доставить экспедицию в Таджуру. Но, немедленно по выходу «Амфитриды» из порта, ее начал преследовать итальянский военный корабль, которому было поручено следить за передвижением русской экспедиции и воспрепятствовать высадке русских на итальянской территории. Одновременно итальянский посол во Франции потребовал от Парижа запретить высадку экспедиции во французские владения, так как, по сведениям итальянцев, русские везли с собой большое количество оружия и тем якобы нарушали конвенцию о запрете ввоза оружия в Африку. Впрочем, итальянской канонерке не удалось помешать высадке миссии: бурной штормовой ночью итальянцы потеряли из виду быстроходную «Амфитриду». Ашиновцы, два дня наблюдавшие за назойливым преследованием итальянцев, ликовали. Атаман по этому поводу устроил даже банкет для капитана и команды корабля.