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