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