Одним из сильных направлений в политике Лужкова всегда оставались его поддержка русскоязычного населения в бывшем СССР, а также государственнические позиции по Севастополю и Крыму. Сформировался этот подход Лужкова не в 1999 году, а гораздо раньше и естественным образом опирался на союз Лужкова с Конгрессом русских общин, руководство которого входило в ядро "Отечества" при его создании.

Однако сложность такой позиции (при ее безусловном патриотическом содержании) всегда заключалась в невозможности разрешить севастопольскую проблему частным порядком, в отрыве от общих российско-украинских отношений и других, гораздо более широких проблем. При этом к концу года Лужков был лишен возможности оставаться на патриотических позициях лишь декларативно.

25.12.98. Госдума ратифицировала российско-украинский договор о дружбе и сотрудничестве. В тексте не оговаривался вопрос сохранения российского статуса Севастополя.

Для Лужкова это было безусловным политическим вызовом. Мэр Москвы должен был возглавить и возглавил кампанию за остановку последующей ратификации договора в Совете Федерации. При этом уже на этапе рафитикации в Думе по блоковым позициям Лужкова был нанесен болезненный удар. В Думе договор активно поддержали предполагаемые левоцентристские союзники Лужкова — КПРФ и "Яблоко", решив этим судьбу голосования.

12.01.99. На заседании политсовета "Отечества" Лужков высказал критическое отношение и к ратификации договора Украины с Россией в части Севастополя, объявив коммунистов предателями Севастополя.

28.01.99. Селезнев высказал мнение, что, выступая против договора с Украиной, некоторые политики делают большую ошибку. Он сказал: "Лужкова попутал бес в лице К.Затулина, которого он держит в помощниках".

Это уже было началом так называемой "войны Селезнева с Лужковым". И упомянутый спикером К.Затулин заявлял об этом напрямую перед ратификацией, считая, что решение фракции КПРФ отражает президентские амбиции Селезнева, стремящегося развести коммунистов и Лужкова.

29.01.99. Лужков ответил Селезневу, что члены СФ "самостоятельно мыслят и принимают решения".

Утратив поддержку в вопросе о договоре "Яблока" и КПРФ, Лужков еще рассчитывал на поддержку региональных лидеров. И на первом этапе рассмотрения добился успеха.

30.01.99. Договор с Украиной в СФ не ратифицировали, Лужков повторил то, что излагал раньше, что это несправедливо, не соответствует статусу Севастополя, который является частью России.

В начале февраля Ю. Лужков подписал распоряжение об учреждении оргкомитета черноморского филиала МГУ в Севастополе. Командование российского ЧФ выразило готовность выделить филиалу МГУ ряд помещений (в том числе Лазаревские казармы) под учебные корпуса и общежития, а также для восстановления океанологической базы.

Однако победа эта была временной. Причем на стадии рассмотрения договора в СФ не оправдались надежды на вышеуказанный "тандем с Примаковым", поскольку именно правительство оказалось главным оппонентом Лужкова в вопросе о ратификации. Логично, что сторонников точки зрения правительства в СФ возглавил К.Титов, создавший вскоре блок региональных лидеров, ориентированный на Е.Примакова.

17.02.99. В Совете Федерации ратифицирован договор с Украиной. За договор отдано 106 голосов.

Наблюдатели прокомментировали такой результат как победу "сенатской партии" Строева над "сенатской партией" Лужкова. Затем Примаков предложил сенаторам "компромисс" — договор вступит в силу, когда Украина одобрит соглашение по флоту.

Показательна картина политических притяжений в Совете Федерации, которую выявило голосование по договору. Среди тех 25 глав регионов, которые поддержали мэра Москвы, оказались почти все зауральские лидеры. Особенное внимание эксперты обращали на единодушие Москвы, Красноярского края и Хакасии. При этом два заявлявших о себе сторонника Примакова как будущего президента РФ — Шаймиев и Наздратенко — от голосования воздержались, избежав, таким образом, обвинений в непатриотичности.

21.02.99. В передаче Е.Киселева Лужков подвел тяжелые итоги дебатов по договору. Он сказал, что Россия впервые потеряла выход в Черное море из Азовского: фарватер тяготеет к Керчи, Украина требует платить за проход по "территориальным водам". А если запретит? В этом договоре, подчеркнул Лужков, нет ничего о праве выхода в Черное море. Турция по Кучук-Кайнарджикскому договору вообще может занять Крым при передаче его кому-либо Россией. А в Черном море уже сейчас сложился военный баланс в пользу Турции — четыре к одному.

Рассматривая последствия кампании в СФ для позиций московского мэра, нужно обозначить, что лидером в Верхней палате парламента Лужков, таким образом, не стал и стать не мог. Более того, в этой кампании он потерял поддержку основных своих политических союзников. В то же время нельзя игнорировать и то, что угроза потери крупнейших политических союзников не заставила мэра отказаться от своих позиций или даже смягчить их.

Потерпев поражение на межгосударственном уровне решения проблемы, Лужков оказался вновь отброшен на уровень межрегиональный и занялся проектом строительства моста через Керченский пролив, который соединил бы Крым с Кубанью.

Далее, в эти же первые месяцы 1999г. Лужков продолжал начатую им в конце прошлого года антибаркашовскую кампанию.