Посетив Абиссинию и будучи там неожиданно хорошо встречен, — кажется, его приняли за какое-то высокопоставленное лицо — Ашинов сам загорелся идеей Хитрово, причем пошел в своих планах гораздо дальше своего вдохновителя. Он решил, что Абиссиния как нельзя лучше подходит для его проекта создания нового казачьего войска, который ему не дали осуществить на Кавказе.
Вернувшись в Россию, Ашинов перво-наперво предложил отправить в Эфиопию русскую духовную миссию для подготовки воссоединения русской и эфиопской церквей и одновременно начал набор добровольцев для заселения якобы уже основанной им на побережье Красного моря станицы «Новая Москва». Станица существовала пока только в его воображении. (Когда привезенные Ашиновым добровольцы высадились на песчаном африканском берегу, они увидели, что разрекламированная Ашиновым станица — это лишь старый полуразрушенный египетский форт, почти не подходящий для жилья, а гавань, которой Ашинов соблазнял морских чинов, мелководна и непригодна для стоянки и бункеровки судов.)
Его предприятие было задумано с размахом. Ашинову поверили даже умудренные опытом государственные деятели, такие, как управляющий Морским министерством адмирал Шестаков и обер-прокурор синода Победоносцев. Лишь Министерство иностранных дел сохраняло свой неизменный скепсис и даже оказывало противодействие его планам. За что Ашинов называл это ведомство исключительно уничижительно Гирска и К°, а его главу— «немец-перец».
Замысел у Ашинова был действительно масштабный. Духовная миссия являлась скорее предлогом, дабы прикрыть политическую подоплеку проекта и привлечь пожертвования. Главное было — занять на красноморском побережье какую-нибудь свободную бухту и создать на ее берегу казачье поселение со стоянкой и угольной станцией для российских судов. Далее атаман предполагал расположить к себе императора Йоханныса IV поставками русского оружия, утвердиться со своими казачками в Эфиопии и образовать там самостоятельное казачье войско из русских выходцев, которое, служа эфиопскому негусу, стало бы одновременно гарантом его лояльности к России.
В марте 1887 года Ашинов обратился в Священный синод с прошением о посылке духовной миссии в Эфиопию. Ашинов в роли духовного начальника миссии желал бы видеть лицо, ему вполне послушное. Поэтому он предложил петербургскому митрополиту Исидору поставить во главе миссии своего старинного приятеля Паисия, состоявшего ключником при православном Пантелеймоновском подворье в предместье Константинополя. Правда, будущий глава духовной миссии был неграмотен и едва мог написать свое имя. Но Ашинова это не смущало, скорее было даже на руку — ничего лишнего не напишет. Однако митрополиту этот выбор показался странным, и он вызвал Паисия в Петербург на собеседование. Благообразный и бесхитростный Паисий произвел на Исидора благоприятное впечатление, и назначение последовало. Духовный сан Паисия — инок — для такого серьезного миссионерского дела оказался слишком мал. Положение решили исправить: 6 августа 1888 года Паисий был рукоположен Исидором в иеродиаконы, 7 августа — в иеромонахи, а 13 — в архимандриты. Немногим монахам удавалось делать столь быструю карьеру. Итак, первый успех был Ашиновым достигнут. Вместе с вполне преданным ему главой будущей духовной миссии Ашинов получил возможность легального сбора пожертвований на миссионерское дело. Сбор пошел споро. Бедствия абиссинских братьев по вере, терпящих от происков католиков, не оставляли русских жертвователей безразличными.
Убедить гражданских чиновников оказалось сложнее. Для успеха плана Ашинову требовалась поддержка Военного и Морского министерств. Военное министерство проект Ашинова о привлечении в союзники абиссинцев не вдохновил. Генерала, к примеру Обручева, изумила просьба атамана отпустить тридцать тысяч винтовок Бердана с миллионом патронов для вооружения абиссинской армии. Управляющий Морским ведомством адмирал Шестаков тоже не хотел воспринимать вольного казака всерьез и долго отказывался встретиться с ним. Однако летом 1887 года их знакомство в конце концов состоялось. Ашинов сумел нащупать чувствительные струнки адмирала: их сблизила общая нелюбовь к англичанам. Кроме того, в некотором содействии проекту Ашинова Шестаков увидел возможность решить ряд задач, стоявших перед его собственным ведомством. «А не поздоровится Джону Булю, коли там и сям крейсерам можно будет запасаться углем», — записал он в дневнике после встречи с Ашиновым.