В ноябре 1998 года в подъезде своего дома была застрелена знаменосец петербургских демократов Галина Старовойтова, которая была еврейкой. Ельцин, у которого она когда-то работала советником, был возмущен и срочно направил в Петербург Путина и министра внутренних дел Степашина для проведения расследования. Позже было установлено, что ее убийство заказали три депутата Госдумы от партии Жириновского, все ведущие фигуры тамбовской ОПГ, которые убедили себя в том, что она была частью еврейского заговора с целью поставить Россию на колени. Несколькими неделями ранее отставной генерал Альберт Макашов заявил на митинге в Москве, что хочет "забрать с собой на тот свет десяток жидов". Дума отказалась снять с него депутатскую неприкосновенность. Путин от имени ФСБ потребовал привлечь Макашова к уголовной ответственности за разжигание межнациональной розни и призвал Думу принять соответствующее решение. Ельцин тоже резко осудил Макашова. Но Минюст и Генпрокуратура Примакова считали, что дело в отношении Макашова не возбуждено.
Мы будем продолжать быть антисемитами, и мы победим, - ликовал Макашов.
В конце концов, антиеврейские волнения утихли. Но Ельцин был недоволен. К тому времени он также начал беспокоиться, что у Примакова, как и у Черномырдина, появились президентские амбиции. Постепенно я начал ощущать опасность ситуации, - писал впоследствии Ельцин. Я понял, что он становится серьезной политической альтернативой моему курсу и моему плану развития страны... [Он] грозил свернуть реформы, обрушить зарождающиеся экономические свободы, растоптать демократические свободы... свободу слова и сохранение системы нормальной политической конкуренции.
К середине апреля 1999 г. президент принял решение, что Примакову придется уйти. Это был щекотливый момент, поскольку Дума, почти год грозившая объявить Ельцину импичмент, наконец-то готовилась вынести этот вопрос на голосование. Ельцина обвиняли по пяти пунктам: ответственность за развал Советского Союза в 1991 году; применение вооруженной силы для разгона Съезда народных депутатов во время осады Белого дома в 1993 году; развязывание незаконной войны в Чечне; ослабление военной мощи России путем непродуманного сокращения бюджета; геноцид народов России путем экономических реформ, приведших к демографическому спаду.
12 мая, за три дня до голосования в Думе, Президент освободил Примакова от должности и выдвинул на его место Степашина. Если бы импичмент прошел успешно, то до новых выборов исполняющим обязанности президента стал бы Степашин, а не Примаков. Ельцин понимал, что это может заставить оппозицию сплотить ряды против него, но не считал это возможным. Резкий, неожиданный, агрессивный шаг всегда выводит противника из равновесия, - пояснил он, - особенно если он непредсказуем и кажется абсолютно нелогичным. Это был урок мастера тактики, который Путин принял близко к сердцу. Когда пришло время голосования, националисты Жириновского отказались участвовать в нем, а некоторые члены "Яблока" воздержались. Ни одно из обвинений в импичменте не набрало большинства в две трети голосов, необходимого для принятия решения. Через неделю парламент утвердил Степашина в должности нового премьер-министра России.
С момента президентских выборов 1996 г. Ельцин был озабочен, если не сказать одержим, тем, как сохранить свое наследие. Глеб Павловский, его политтехнолог, вспоминал, как в августе того года Чубайс, только что назначенный руководителем Администрации Президента, созвал совещание ближайших помощников Президента. Он сказал, что Ельцин больше не будет баллотироваться. Главной задачей второго срока будет поиск достойного преемника.
Ельцин изначально рассматривал Бориса Немцова как возможного кандидата. Во время своего первого срока он посетил Нижний Новгород, где Немцов был губернатором, и был впечатлен его энергией. Он говорил о нем Биллу Клинтону и Гельмуту Колю как о молодом человеке, у которого есть будущее. Но, уговорив его приехать в Москву весной 1997 года, Ельцин был разочарован. Немцов, решил он, как и Чубайс, - "технолог, менеджер, специалист, [а не] национальная фигура, способная консолидировать целые слои общества". Черномырдин и Примаков были представителями другого поколения, не готовыми к реформам и неспособными вести Россию в наступающий новый век. Правительство Кириенко было "управленческим, технократическим... и не имело политической поддержки - ни авторитета, ни влияния на общество". Ельцин рассматривал и другие варианты, но быстро их исключил. Лидер "Яблока" Григорий Явлинский был "хорошей, сильной фигурой", но сектантской и слишком привязанной к своей фракции. Игорь Иванов, министр иностранных дел, был союзником Примакова.
Более серьезным претендентом был министр путей сообщения Николай Аксененко. Ельцин считал его отличным экономическим плановиком и возможной альтернативой Кириенко и Степашину. Но большинство Думы его недолюбливало, и Ельцин пришел к выводу, что его лучше держать в резерве. Он так и остался потенциальным преемником, который так и не смог реализоваться.