Два тижні пізніше окремий посланець від регентки привіз Галіцинові наказ арештувати Самойловича, відіслати до Москви і негайно вибрати нового гетьмана.
Галіцин казав уночі оточити своїм військом головну квартиру Самойловича і передав до відома козацьким старшинам наказ своєї володарки.
Коли гетьман, прокинувшись уранці, побачив, що його шатра сторожать московські вояки, він зрозумів усе своє лихо. Та як звичайно і цього ранку вій пішов до похідної церкви. Після богослужіння підійшов до нього один із полковників і, вхопивши його різко за плече, гукнув: "Пане гетьмане! військо зве тебе".
Гетьман вийшов мовчки із церкви.
На нього впала буря прокльонів, докорів й обвинувачень. Бачили, як київський полковник погрожував йому навіть сікачем, яким вимахував над його головою.
Казали сісти Самойловичеві на нужденнім візку, а його синові наохляп на худощаву кобилу і так завезли їх до головної квартири Галіцина.
Князь скликав козацьку старшину, яка знову повторила свої обвинувачення проти Самойловича. Він пробував надаремне виправдуватись; збори переривали йому весь час криками та погрозами, не даючи змоги роз'яснити справу. Його вивели і відіслали до Москви; там він коротав свої останні роки на засланні.
26 червня відбулись вибори на нового гетьмана. Козаки у рядах несли святочно до військової каплиці гетьманські відзнаки: бунчук та булаву.
Галіцин вийшов зі свого шатра на підвищення і так промовив голосно до козаків: "Козаки, виберіть собі гетьмана і за стародавнім звичаєм своїх батьків назвіть його одноголосне".
Настала велика мовчанка, а за нею знявся величезний крик, наче грім: "Мазепа, Мазепа, нехай Мазепа нам верховодить!"
Галіцин повторив кілька разів своє питання і на це дістав ту ж, однозгідну відповідь.
Тоді думний дяк із Москви вийшов на трибуну і прочитав переяславський договір, підписаний Хмельницьким і царем, основний акт, що з'ясовував взаємини між Україною і Москвою. Козацька старшина підписала папери, які їй предложили, і новий гетьман, склавши присяги на Євангелії, почав урядувати.
Кілька днів пізніше Мазепа у своїй головній квартирі дав великий обід у честь Галіцина. Вистріли артилерії віщували радісно степам про появу нового володаря України…
Мазепа осягнув перші щаблі, намічені своїм себелюбством. Треба було закріпити придбані позиції та підсилити свій авторитет, якому невпинно загрожували дві сили: московські Інтриги і козацька самоволя. Москва була недовірлива та підозрілива; її бояри любили гроші, її дипломати радо слухали наклепів козацької старшини, піддержували непорозуміння між ними, вічно цькували згідно зі старим принципом divide et empera, щоб тільки вдержувати Україну у стані невпинного безладдя.
Самойлович залишив на рідній землі приятелів і прихильників; їх позвільнювали зі становищ, одного за одним, а меткіших відіслали до Москви.
Козацькі верхи були завсіди небезпечні. Мазепа пробував якомога зручно цю небезпеку звести нанівець. Своїм старшинам роздавав він почести, побільшував їхні багатства та землі і одночасно підтримував проти них недовірливість Москви. Коли його могутній союзник домагався вжити проти підозрілих осіб насильних засобів, гетьман боронив їх явно і таким робом з'єднав собі вдячність серед тих небезпечних елементів, зв'язуючи їх навіки зі своєю долею.
У 1689 р. рішили піти новою війною на кримського хана. Галіцин із допомогою Мазепи взяв провід у цій виправі, яка на цей раз удалась. Татарів побили, Перекоп відібрали, і хан мусив прохати миру. Коли треба було з'ясувати мирові умови, Галіцин радився Мазепи, але хитрий гетьман, лякаючись відповідальності, не виявив своєї думки. Галіцин тріумфально вернувся до Москви; приймали його там із почестями. Та це був його останній успіх; панування Софії кінчалось, і Петро вже ладився перебрати владу.
Небавом і Мазепа приїхав до московської столиці. Показався він там із незвичайною пишнотою у товаристві найбільших козацьких достойників: генерального обозного, генерального писаря, генерального судді, генерального осаула та генерального бунчужного. Найбільші українські міста мали серед його дружини своїх полковників і поважний Чернигів, і люба Полтава, і торговельний Ніжин, і Новгород, оспіваний згодом Гоголем, і Лубни, де півстоліття тому панував жорстокий князь Ярема Вишневецький, прогнаний Хмельницьким. Гетьманська дружина мала більш триста осіб.
Ніколи ще Москва не бачила українського гетьмана у такій пишноті. Здавалось, що вона приймає не васала, а могутнього союзника і справжнього володаря. Чимало царської кінноти та піхоти виїхало назустріч козацькій дружині. Царська карета ждала на Мазепу при воротах Москви, і один високий достойник в імені царів і Софії питав, як здоров'я гетьмана. Так наказувала давня византійська етикета.
Мазепа зайняв місце у кареті з козацькою та московською дружиною перед нею і поза нею; він в'їхав до міста через ворота від Калуги, переїхав ріку Москву через міст на човнах і зупинився у славному посольському дворі де на нього ждали апартаменти.
Гетьман не знав, що діється на дворі, не догадуючись, що дні панування Софії та Галіцина вже почислені. У своїх розмовах із московськими комісарами, які мали перевірити його настрої, він вихвалював подвиги царського улюбленця:
– Ніколи ще невірні не мали такого страху, як перед князем Василем Василевичем Галіциним! Яка шкода, що забракло нам води і ми не могли зруйнувати Перекопу.
І до цього ще докинув такий коментар на доказ своєї вченості:
– Давні хронікарі кажуть нам, що перський цар Дарій. коли йшов завойовувати Крим із хмарами війська, не міг узяти Перекопу, бо бракло йому води, а відступаючи, поклявся, що ніколи більше не вернеться на Крим.
На другий день на Кремлю було велике прийняття. На ньому вихваляли подвиги Галіцина та Мазепи, якому в імені царя передали багаті дарунки: срібну вазу та золотий пояс, прикрашений брильянтами. Мазепа віддав візит цареві Іванові, напівідіотові, патріархові та не міг зустрітись із Петром.
Гетьман був іще у Москві, коли дійшло до соuр d'Etat: Софію зачинили у Дівочому монастирі, Галіцинові відібрали його майно і заслали, Іван якби й не існував, і велика Петрова доба почалася.
Мазепа мучився здогадами, що буде далі: його оточення вже намічувало його наслідника і сам гетьман тратив уже надію.
Він хотів заграти ще свою останню карту і зі своєю дружиною відвідав Петра у Троїцькому монастирі.
10 вересня молодий цар Петро, тоді 17-літок, прийняв українців на аудієнції і тут іще раз могутній чар Мазепи взяв верх. Мазепа приніс із собою багаті гостинці; великий золотий хрест, викладений самоцвітами, прегарну шаблю, яку наївний хронікар цієї доби оцінює на 2000 рублів, і золоті нашийники для царської рідні. Та більш як усіма дарунками вмів він з'єднати собі приязність царя своїм красномовством, своїм незрівняним хистом переконувати людей. Жаль, що ця майстерна промова найзручнішого дипломата у тодішній Європі якось не збереглась і не дійшла до нас.
Мазепа покинув Москву 12 вересня 1689 р. у ще більший силі та славі, ніж мав її, коли туди приїхав. В останніх днях його побуту у московській столиці трапився один дивний і дуже характеристичний епізод.
Польща, як відомо, ніколи не хотіла зректись України, і польський король Ян Собеський пробував з'єднати собі Мазепу через француза Невіль, тайного агента, якого вислав до Москви маркіз Бетюн, тодішній представник Людовика XIV у Варшаві. Невіль мусив доказати неабиякої штуки, щоб виконати свою місію, бо москалі XVII віку були дуже підозріливі і звикли стежити назирці за чужинцями. Французький агент переодягнувся і у товаристві одного німецького лікаря, що мешкав віддавна у Москві, зумів знайти доступ до Мазепи. Цей відкинув пропозиції польського короля. Чужинний посередник, хоча і зазнав повної невдачі, не почував жалю до Мазепи; у своїх споминах він згадує про "велику вченість того князя, який володіє прегарно латинською мовою".
Гетьман мусив поквапно вертатись, бо на Україні збиралось на бунт. Заки виїхав до Москви, він залишив на відчинених кордонах сильні обсади. Але татари не рухались і небезпека приходила із середини: вже поширювались чутки, що цар заарештував Мазепу, щоб заволодіти Україною. Запорожці проводили цим рухом; вони вислали послів до кримського хана і польського короля з пропозицією приєднатись до них проти Москви, яка наважилась на їхні вольності.
Якби Мазепа був хотів, він міг би був дати собі раду з царем, який не міг боронитись. Але він не хотів єднатись із Польщею. Він завів лад і при помочі своїх агентів у Варшаві та на Кримі вмів подати до відома, що Польща, втомившись турецькою війною, почала переговори з Портою, не розпитавши про думку свого московського союзника. Мазепа повідомив про це негайно царя, який був йому вдячний за таку важну звістку.
