В тот же день новоизбранный гетман подписал с московскими послами новое соглашение, так называемые Коломакские статьи. В целом, они повторяли Глуховские статьи 1669 года с дополнениями, внесенными в период гетманства Самойловича. Казацкий реестр определялся в 30 тысяч, гетман не мог снимать полковников без соответствующего царского указа, ему запрещалось поддерживать самостоятельные дипломатические связи с други ми государствами, в главных городах Украины оставались царские гарнизоны. При этом Коломакский договор впервые обязывал украинское правительство «народ малороссийский всякими меры и способы с великороссийским народом соединять и в неразорванное и крепкое согласие приводить супружеством и иным поведением».
Таким образом, подписанные И. Мазепой при получении гетманской булавы обязательства ставили Левобережную Украину в еще большую зависимость от Московского царства, чем при его предшественниках. Но это не помешало И. Мазепе вынашивать далеко идущие планы объединения под своей булавой всех украинских казацких земель вместе с Правобережьем и Запорожьем. Объединенная Украина представлялась ему в пределах государства Богдана Хмельницкого, летом 1668 года почти восстановленного П. Дорошенко.
С падением Софьи и утверждением на престоле в Москве Петра I Мазепа ничего не потерял. Привлекая молодого царя своей образованностью, «европейскостью» и широтой политического кругозора, он быстро вошел в доверие к всероссийскому самодержцу, помогая ему дельными советами и обеспечивая стабильность на всем пространстве от Днепра до Дона. Под командованием Мазепы украинские полки принимали участие в Крымском походе 1689 года, овладении Казикерманом в 1695-м, осаде и взятии Азова в 1696-м, последующих затем Азовских походах второй половины 1690-х годов. Безупречно выполняя поручения Петра, И. Мазепа окончательно расположил к себе молодого царя, развязав себе руки для борьбы за расширение своей власти на Правобережье.
Правобережная Украина после Чигиринских походов турецко-татарских войск до самого Поросья лежала в руинах. Вместе с тем, продолжавший войну с турками король Ян III Собеский принял меры для восстановления на возвращенных под власть польской короны землях казацких полковых структур, способных противостоять татарским набегам. Среди местных лидеров здесь выделялся Семен Палий, долгое время проведший на Запорожье. Прославившись в борьбе с татарами, он лелеял надежду освободиться от польской власти, в чем рассчитывал на поддержку Московского царства. С этой целью он сблизился с И. Мазепой и через него обратился в Кремль с просьбой принять его с правобережными казаками в российское подданство.
Московское правительство, находясь в то время в союзе с Речью Посполитой против Османской империи, не хотело портить отношения с Варшавой. Поляки, проведав о намерениях Палия, схватили его, но тот вскоре бежал и в Фастове, под Киевом, у границы королевских и царских владений, поднял против Речи Посполитой восстание.
Семену Палию удалось разбить шляхетское ополчение, и в октябре 1702 года он овладел Бердичевом, а затем Немировом и Белой Церковью, распространив свою власть на все Правобережье и Восточную Подолию. Ему способствовало то, что в начавшейся в 1700 году Северной войне, в которой против господствовавшей на Балтийском море Швеции выступили Россия, Речь Посполитая, Саксония и Дания, польские войска, сосредоточенные на севере, терпели жестокие поражения.
Резиденцией С. Палия стала Белая Церковь. Отсюда он слал письма Петру I и Мазепе с просьбами о переходе в российское подданство, однако царь, не желая портить отношения с союзниками, через левобережного гетмана убеждал Палия подчиниться полякам. Ввиду усиливавшейся на территории Речи Посполитой анархии, И. Мазепа по приказу Петра I весной 1704 года выступил на Правобережье. С. Палий откликнулся на его приглашение и прибыл в лагерь гетмана, где в конце июля того же года был задержан и обвинен в сношениях с врагами российского царя и польского короля — польскими сторонниками шведов во главе с гетманом Любомирским. Затем он был выдан российской стороне и после учиненного с обычной для петровских времен жестокостью дознания сослан в Сибирь.
Шведский король Карл XII.
Иван Мазепа не только избавился от популярного в народе соперника, но фактически стал хозяином всей Правобережной Украины. Против этого Петр I не возражал. Войска его союзника, польского короля Августа II, были разбиты еще в 1702 году, и Карл XII, заняв Варшаву и Краков, летом 1704 года посадил на престол Речи Посполитой своего ставленника Станислава Лещинского. В такой ситуации, при том, что российские войска противостояли шведам в Прибалтике и Белоруссии, Петр был заинтересован, чтобы Украина западнее Днепра, формально не включаясь в состав его царства (во избежание конфликта с союзными ему силами в Польше), находилась в руках доверенного человека, каковым в то время и являлся И. Мазепа.