Вначале Саакашвили поддерживал хорошие отношения с Кремлем и обещал восстановить железную дорогу из Абхазии в Армению. Он пытался склонить на свою сторону Эдуарда Кокоиты, пообещав полу-автономию для Южной Осетии и помощь с экономическим развитием, но Кокоиты, оказавшийся заложником осетинских националистов, не клюнул на приманку. В июле 2004 года осетинские милиционеры похитили пятьдесят грузинских полицейских, заехавших на территорию Южной Осетии. Саакашвили опрометчиво потребовал в ответ, чтобы русские убрали из Южной Осетии бо2льшую часть «миротворцев». Русско-грузинское согласие на этом завершилось: разрыв произошел, когда Саакашвили объявил, что Грузия присоединится к НАТО независимо от мнения России и что он отказывается «финляндизировать» свою страну. 18 августа вспыхнула двухнедельная стычка с осетинами, которую Саакашвили прекратил только после давления дипломатов. Путин уже стал непреклонным личным врагом Саакашвили, и новый лидер абхазов Багапш прервал переговоры с Грузией. Когда в декабре 2004 года Саакашвили недвусмысленно поддержал Оранжевую революцию в Украине, Путин поставил цель избавиться от него.
Вступив в конфронтацию с Россией и с сепаратистами, Саакашвили выигрывал в глазах грузинской публики. Но и с грузинами его медовый месяц заканчивался.
3 февраля 2005 года было объявлено, что премьер-министр Зураб Жвания с заместителем уполномоченного президента Грузии в регионе Квемо-Картли Раулем Юсуповым погибли от отравления угарным газом в наемной квартире, где собрались ночью, якобы чтобы сыграть партию в нарды. Телохранитель давал противоречивые показания, даже фотографии квартиры менялись (без окурков, с простыми окурками, с окурками, скрученными, как их скручивал Жвания) с каждым выпуском газет; тела торопливо предали земле, врачи-патологоанатомы и журналисты подвергались избиению или умирали таинственной смертью. Вызвали экспертов из ЦРУ, но они смогли проверить только иранскую печь и вентиляцию квартиры: в английском заключении ЦРУ говорится, что окиси углерода недостаточно (а в грузинском переводе «больше чем достаточно»), чтобы причинить смерть. До сих пор все, кроме поклонников Саакашвили, задаются вопросом, при каких обстоятельствах погиб Жвания — не в результате ли ссоры или потасовки в президентской резиденции? Но то, что последовало, — убийство Юсупова, установка иранской печи (с даже не просохшей еще штукатурой), нелепая фальсификация вскрытия (в желудке Жвания будто бы нашли остатки продуктов, которых он никогда не ел), неуклюжая попытка инсценировать гомосексуальное свидание, — объективному наблюдателю показалось бы вопиющим государственным преступлением. Известно, что после распада Советского Союза в Тбилиси КГБ оставил достаточно токсикологических материалов, чтобы служба безопасности могла легко симулировать смерть от инфаркта или угарного газа. Почти все министры, уволенные впоследствии Саакашвили, намекали, что Жванию убили.
Саакашвили начал работать больше с группой советников, чем с министрами, которых он увольнял и нанимал слишком часто, чтобы они могли войти в курс дела. Кроме Гига Бокерия, только Вано Мерабишвили, министр внутренних дел и госбезопасности, силовик, который осваивал огромную часть бюджета, оказался незаменимым. Именно Мерабишвили, расспространив часа через два-три после смерти Жвания информацию, что причиной смерти является угарный газ, намекнул, что лучше не вникать в дело, чтобы не опозорить близких фактом гомосексуального свидания. Гиорги Барамидзе, друг Жвания, продолжал пользоваться доверием Саакашвили.
Потеря умного и в отличие от президента толкового премьер-министра все-таки была менее катастрофична для правительства, чем отставка Саломэ Зурабишвили 19 октября 2005 года после ее протеста, направленного на подрыв президентом дипломатии и вмешательство парламента в назначение дипломатов. Те, кто не пользовался доверием Саакашвили, становились статистами в театре грузинского управления.
Каха Бендукидзе оставался у власти дольше других, до февраля 2009 года: благополучие страны зависело от его энергии и предприимчивости. Приватизация проходила очень быстро: всем было все равно, что государственные предприятия продавали нелепо дешево людям, которых разыскивал Интерпол: главное, чтобы Грузия теперь считалась «другом бизнеса», урезав бюрократию. Турецким компаниям отдали наземные пограничные пункты и два международных аэропорта Батуми и Тбилиси. По завершении приватизации Бендукидзе стал ректором экономического университета.