На другий рік, коли в Криму призначили нового хана, Петрик переконав його йти разом війною на царя. Знову звернувся з відозвою до запорожців, але, як і минулого року, не вся Січ відгукнулася. Дозволили йти тільки охочим. Об'єднані сили дійшли до Полтави, де знову повторилася тогорічна ситуація — татари покинули Петрика.
У 1695 р. він знову ходив з ордою, писав універсали, однак із таким же фіналом, як і в попередні два походи. Мазепа ходив проти Петрика в походи ще й у 1694, 1696 роках. Нарешті гетьман пообіцяв тисячу карбованців тому, что вб'є Петрика. Такий охочий на прізвище Вечірченко знайшовся. Він наздогнав Петрика й проколов його списом, але й сам був убитий.
У перші роки XVIII ст. склалася така політична ситуація, яку Іван Мазепа міг використати для поширення своєї влади на Правобережжі, що за Андрусівським перемир'ям і Вічним миром залишалося за Польщею. Це дало б йому змогу об'єднати дві частини України й зробити перший крок на шляху до незалежної самостійної української держави. Проте здійснення цього наміру вступало в суперечність із особистими стосунками Мазепи та Семена Палія, якому належала головна заслуга у відновленні козацтва на Правобережжі. Мабуть, нелегку внутрішню душевну драму довелося пережити Мазепі в цих обставинах.
Семен Палій, фастівський полковник, талановитий військовий керівник і організатор, мав добру освіту й був людиною великої хоробрості. Він пройшов військову школу в Петра Дорошенка, часто бував на Запорозькій Січі, уславився успішними походами на Кримське ханство й турецькі фортеці в пониззі Дніпра, брав участь в обороні Відня від турків.
Разом із полковниками Іскрою, Абазином і наказним гетьманом Самусем організував козацьку колонізацію правобережних земель, які внаслідок руїни здебільшого являли собою пустелю: міста й села лежали в руїнах, населення було знищене або розбіглося. Зовсім порожньою, незаселеною залишалася за договором із Москвою ціла смуга землі від Києва до Чигирина, яка мусила правити за своєрідний буфер між Лівобережною Україною і володіннями Польщі. Річ Посполита потребувала постійної охорони своїх українських володінь від татарських нападів. Отож польський король Ян Собеський у 1684 р. видав універсал, що дозволяв козакам селитися в місцевостях, де лежали зруйновані міста Корсунь, Чигирин, Лисянка, Умань, а в 1685 р. сейм прийняв постанову відновити на Правобережжі козацтво, яке дістало змогу розселятися по всьому краю.
Заселення відбувалося швидкими темпами. Виникали козацькі полки не тільки як військові, а й як адміністративно-територіальні одиниці з козацьким ладом, козацьким вільним хліборобством на родючих чорноземних незайнятих грунтах. Палій, установивши свою резиденцію у Фастові (60 кілометрів від Києва), поводив себе як ні від кого не залежний володар. Це викликало тривогу й невдоволення і польського, й московського урядів.
Палій мріяв відтворити всі полки правобережного козацтва й передати його під владу лівобережного гетьмана, щоб об'єднати розрізнені частини України. У 1688 р. він через гетьмана Мазепу звертався до московського уряду з проханням прийняти його разом із фастівським полком у підданство. Але царський уряд не хотів порушувати угоди з Польщею. У 1699 р. польський сейм після замирення з Туреччиною, яка остаточно зреклася своїх претензій на Правобережну Україну, постановив скасувати тут козацтво, позаяк воно вже було непотрібне як охорона.
Палій, Самусь та інші полковники «не підкорилися й у 1702 р. підняли на повстання народ Київщини, Волині та Поділля. У ряді битв вони розбили польські війська, здобули сильно укріплену фортецю в Білій Церкві, оснащену багатьма гарматами, запасами пороху й амуніції.
Таємно Палій підтримував тісні контакти з лівобережним гетьманом Мазепою. У 1694 р. він писав гетьману: «Я знайшов цей край пустелею й працював коло Хвастова, як коло свого хазяйства. Широкі поля засіялися збіжжям, число мешканців зросло, та не так із польської сторони, як із берегів Дніпра, з козацького краю та з Волощини; й церкви Божі я побудував і прибрав на славу Божу».
Мазепа радив цареві, щоб той прийняв під свою владу Правобережну Україну, принаймні Білу Церкву. Але вже розпочалася Північна війна, й Петро І, який оголосив війну Швеції, бажав заручитися польською допомогою за рахунок Правобережжя України. Не приймаючи Палія у своє підданство, цар вимагав від Мазепи, щоб він відписав Палію про необхідність припинення повстання й підкорення полякам. Щодо самого гетьмана, Петро І заборонив йому надавати допомогу повстанцям.
Мазепа пропонував Палію згідно з царським указом миритися та уступати полякам, а водночас до Москви писав: «Не можу брати гріха на душу та привітними запевненнями намовляти Палія, Самуся та Іскру до послуху, а опісля віддавати їх полякам у неволю. Я не можу запевняти їх, що вони остануться цілі й неушкоджені, як у своєму здоров'ю, так і в маєтках. Поляки не тільки над козаками, але й надо всім українським народом, що опинився під їхньою владою, по-тиранськи поводяться. Це ж показали їхні недавні діла на Придністрянщині й на Побужжі, де вони мстилися за народне повстання, багатьох карали смертю, вішали, кидали на цвяхи або саджали на кіл…»
Повстання було придушене поляками, хоча їм довелося подолати відчайдушний опір, перебороти героїчну оборону. Загинуло десять тисяч при обороні Ладижина, тисячі покарано на смерть. Тільки Палій тримався у своїй Білій Церкві. Польський гетьман Синявський прохав Мазепу допомогти йому в боротьбі з повстанцями. Але український лівобережний гетьман надавав допомогу своїм землякам, рятував козаків від репресій. Він прийняв у себе Самуся, котрий віддав йому свої гетьманські клейдони.
Весною 1704 р. Мазепа одержав наказ Петра йти з усім своїм військом углиб Польщі, щоб підтримати союзника царя — польського короля Августа II. Польща тоді розділилася на дві партії. Значна частина магнатів перейшла на бік Станіслава Лєщинського, якого згодом Карл XII посадив на престол.
Для Мазепи настав слушний час здійснити давній намір, свою заповітну мрію — об'єднати всю Україну під своїм проводом. З 30-тисячною козацькою армією він перейшов Дніпро, зайняв Київщину й Волинь і вирішив звідти не відступати. За проханням царя Петра й короля Августа Мазепа розправився з магнатами, прибічниками Станіслава Лєщинського, подолавши їхній збройний опір.
Свою головну квартиру Мазепа розмістив у Бердичеві. Її часто відвідував Семен Палій, якого Мазепа завжди зустрічав якнайкраще. Водночас йому було треба виправдатися перед царем Петром і королем Августом, легітимувати своє військове утвердження на Правобережжі. Щоб закріпити свій політичний успіх, лівобережний гетьман вирішив пожертвувати Палієм, хоч їх і об'єднували патріотичні почуття до України, спільна політична мета. Цар велів узяти Палія під варту і негайно відправити в Білу Церкву, замість нього полковником призначити Михайла Омельченка.
Першого серпня Семен Палій прийшов до головної квартири Мазепи. Його прийняли бенкетом. Вночі, коли полковник міцно заснув, його схопили й силоміць вивезли до Батурина, а звідти вислали до Москви. За зв'язки з прихильником Лєщинського Любомирським Палія звинуватили у шведофільстві й заслали до Сибіру.
Деякі дослідники пояснювали усунення Палія Мазепою їхньою взаємопротилежною соціальною політикою. Мазепі не до вподоби був демократизм Палія, який встановив у своїй «палієвій державі» порядки, близькі до ладу Запорозької Січі. Крім того, він ворогував із українською шляхтою. Вважали навіть, що Мазепа вбачав у фастівському полковникові можливого суперника — претендента на гетьманську булаву. У всякому разі народна пісня засудила віроломство Мазепи щодо Палія, зробивши акцент на моральному сенсі цієї події. Палій виступає в пісні як народний герой, «козацький батько».
У жовтні 1704 р. Мазепа, залишивши на Правобережжі козацькі загони, повернувся до Батурина як справжній володар України. Він уживав титул — «Гетьман обох сторін Дніпра».
Менш за все висвітлено в літературі полководницьке мистецтво Івана Мазепи. Дехто з істориків навіть намагався стверджувати, що Мазепа не був добрим вояком, показав себе поганим стратегом і недосвідченим військовим керівником, ухилявся від битв, вважав за краще посилати замість себе наказних гетьманів. Однак такі твердження не відповідають дійсності. Ще в юні роки він прилучився до вивчення військової справи. Посланий королем Яном-Казимиром для навчання за кордон. Мазепа на кошти мецената краківської академії Новодворського спеціально вивчав гарматну справу у Франції і Голландії, оволодів майстерністю виробництва гармат. Товаришував з ним майбутній полковник артилерії Мартин Катський.
