Вплотную созданием военной организации Андрей Иванович занялся в Петербурге со второй половины 1879 г. Прежде всего, он обратил внимание на морских офицеров. Начиная с шестидесятых годов, разночинцы все сильней проникали и в армию. К ним по своим воззрениям и образу жизни были близки и дети обедневших дворян. Неудачи турецкой кампании, николаевские порядки, муштра, смотры, привлечение воинских частей к подавлению крестьянских бунтов, польского и окраинных восстаний, несение полицейской службы, радикальные веяния, Фейербах, Чернышевский, Писарев, Добролюбов, Некрасов, нелегальная литература — толкали чутких офицеров в революционную среду. Морское офицерство, наиболее образованное, часто к тому же находилось в заграничных плаваниях и наблюдало, как живут в других странах. Низшие чины тоже порою были уже подготовлены к восприятию революционных идей. Это подтверждает опыт Нечаева в крепости; если же Исполнительный комитет обратился прежде всего к офицерскому составу, то к этому его понуждали обстоятельства. Офицерская среда была ближе народникам-интеллигентам, чем солдаты. Она являлась наиболее благоприятной для заговора: чувство товарищества, замкнутость, дисциплина, привычка спокойно глядеть в глаза смерти, уменье обращаться с оружием, все это было крайне необходимо для тогдашнего подполья. Участники народовольческой военно-революционной организации неоднократно рассказывали, с какой гадливостью офицеры, даже патриотически настроенные, относились к предателям и доносчикам. Случалось, противники революционного движения из чувства кастовой солидарности предупреждали товарищей об обысках, арестах и засадах. К офицерству, в особенности к морскому офицерству, Исполнительный комитет должен был обращаться в первую очередь еще и потому, что здесь скорее всего можно было получить динамит, запалы, специалистов.
Андрей Иванович, не оставляя работы по непосредственной подготовке покушений на царя, со всей страстностью и упорством отдался созданию военной организации. Участник морского кружка, Серебряков, превосходно изобразил Желябова-пропагандиста среди морских офицеров, и хотя воспоминания эти неоднократно приводились, обойтись без них и сейчас трудно. По рассказу Серебрякова Н. Суханов однажды пригласил его в числе других товарищей к себе на собрание.
— У него мы застали большую компанию офицеров и двух штатских, которых Николай Евгеньевич представил нам, назвав одного Андреем, долгого Глебом.
Сначала разговор шел об общих предметах, мало интересных. В разговоре я не принимал почти никакого участия, а все свое внимание сосредоточил на присутствовавших штатских, желая разгадать, кто из них интересующий меня член Исполнительного комитета. Назвавшийся Андреем был замечательно красив: высокого роста, с темно-русыми бородой и волосами; серые глаза его, казавшиеся темными, были замечательно живы и выразительны. Другой — невысокого роста, с лицом, почти совсем закрытым густой черной бородой, с проницательными черными, как уголь, глазами…
Разговор продолжался недолго. Немного времени спустя после нашего прихода Суханов прервал разговор и, обратившись к присутствующим, сказал:
— Господа, эта комната имеет две капитальные стены; две другие ведут в мою квартиру; мой вестовой — татарин, почти ни слова не понимающий по-русски; а потому нескромных ушей нам бояться нечего, и мы должны приступить к делу. Потом повернувшись к высокому штатскому, прибавил: — Ну, Андрей, начинай!
Тогда штатский, назвавшийся Андреем, встал и, обращаясь к офицерам, произнес с большим энтузиазмом длинную, горячую речь.
— Так как Николай Евгеньевич передал мне, — начал он, — что вы, господа, интересуетесь программой и деятельностью нашей партии, борющейся с правительством, то я постараюсь познакомить вас с той и другой, как умею; мы, террористы — революционеры, требуем следующего…
Трудно передать впечатление, произведенное на присутствующую публику этой речью. Все, бывшие в этот вечер у Николая Евгеньевича, за исключением нас, не были подготовлены услышать подобную смелую речь. Все они привыкли говорить о правительстве, особенно же о революционных партиях, только в своих тесных кружках и то в известной форме. Никому из них Николай Евгеньевич не сказал, кто у него будет; и они даже не подозревали, с кем имеют дело. Суханов всех, кто ему нравился, приглашал к себе по одному и тому же способу: "приходите ко мне тогда-то, у меня хороший человек будет", — говорил он и больше объяснений никаких не давал.