Летом 1993 года, после расстрела на таджикско-афганской границе российской погранзаставы президент России снял со своей должности командующего погранвойсками Владимира Шляхтина и назначил на нее занимавшего тогда пост первого замначальника Генштаба Андрея Николаева. Тогда это выглядело как ссылка, потому что находящиеся в более чем плачевном состоянии войска, казалось, могло спасти только чудо. К тому времени уже стало ясно, что Николаева все равно придется уйти: у него не сложились отношения с начальником Генштаба Михаилом Колесниковым.
Но Николаев неожиданно пошел в гору. Благодаря давнему знакомству с президентом (отец Николаева был дружен с Ельциным) он добился увеличения ассигнований на созданную после разгона Министерства безопасности самостоятельную Федеральную погранслужбу, навел относительный порядок как во вверенных ему войсках, так и практически на всем периметре границ Содружества.
Первым опасность почуял Павел Грачев, и несколько месяцев между ним и Николаевым шла открытая война — Грачев предлагал переподчинить ФПС Министерству обороны. Но к тому времени голыми руками Николаева было уже не взять, и он отбился. И одновременно стал, по мнению наблюдателей, одним из главных претендентов на пост военного министра.
Однако после отставки Грачева в июне 1996 года, как утверждают, Николаев от предложенного ему поста министра обороны отказался: то ли на этом предложении никто особо не настаивал, то ли сам Николаев понимал, что возглавлять армию, на которую нет денег, бессмысленно. Возможно, свою роль в неназначении Николаева сыграла его январская размолвка с Ельциным. Тогда, после захвата Радуевым дагестанского города Кизляр, президент заявил: "Пограничники проспали". Николаев не долго думая подал прошение об отставке. Президенту это не понравилось: мол, нашелся умник.
Тем не менее Николаев сейчас пользуется расположением президента и вполне может рассчитывать на должность министра обороны или начальника Генерального штаба.