Тоді Мазепа за царським наказом перейшов на правий бік Дніпра, нібито вирушаючи проти шведів, і почав скликати до себе козацьких начальників. Прибув до нього Самусь і поклав перед ним свої гетьманські знаки. З'явився й Палій, який сподівався, що тепер, нарешті, російський цар прийме його у підданство і здійсниться давнє його бажання. Мазепа затримав Палія у своєму таборі, вочевидь, по-дружньому, а між тим зголошувався з Головіним і запитував, що слід вчинити з Палієм, котрий, як доповідав Мазепа, перебуваючи в гетьманському таборі, постійно пиячив. Головін наказав запропонувати Палієві їхати до Москви, а якщо він відмовиться, то дізнатися – чи не прихильний він до ворогів Росії і, в разі викриття в такій прихильності, заарештувати його. Викривачі Палія одразу ж знайшлися: якийсь хвастівський іудей посвідчив, що Палій спілкувався з гетьманом Любомирським, який став тоді на бік Карла XII, і Любомирський обіцяв Палієві прислати грошей від шведського короля. Свідчення орендатора-єврея підтвердив священик Гриць Карасевич. Мазепа, простоявши декілька днів табором у містечку Паволочі, в кінці липня 1704 року перейшов до Бердичева і там, запросивши до себе Палія, напоїв його доп'яна, потім наказав закувати і відправити до Батурина, де вартові здали Палія разом з його пасинком російським властям. За царським наказом його відправили на довічне заслання в Єнісейськ.
Так у злагоді з російським урядом розправлявся Мазепа з народними елементами у південній Русі, ворожими польсько-шляхетському спрямуванню. Російський цар все більше й більше благоволив Мазепі і вважав його серед усіх, які були, малоросійських гетьманів єдиним, на котрого сміливо міг покластися російський уряд. Під час взяття Азова (16) Мазепа охороняв біля Коломака російські кордони від татар, а п'ятнадцять тисяч його козаків під проводом чернігівського полковника Лизогуба (17) відзначилися під Азовом. За це найбільше од усіх цар винагородив самого Мазепу. Іще в 1696 році, після взяття Азова, цар бачився з ним у полковому місті слобідських полків Острогозьку і одержав від нього в подарунок турецьку шаблю з дорогоцінною оправою і щит на золотому ланцюгу, а гетьманові віддарував шовковими тканинами та соболиними хутрами. У 1700 році цар зробив Мазепу кавалером установленого ордена Андрія Первозванного. У 1703 році Петро подарував йому Крупицьку волость у Севському повіті. У шведській війні брали участь козаки без Мазепи, під керівництвом інших начальників, а царську вдячність за їхні подвиги одержував малоросійський гетьман. Стараючись ще більше увійти в милість до царя, Мазепа у своїх донесеннях весь час скаржився на бунтівливий дух підлеглих йому малорусів, особливо лаяв запорожців. В одному лише розходився гетьман з царем: гетьман постійно вважав можливим і корисним повернути у підданство Росії правобережну Малоросію, відступлену Польщі; Петро не схилявся на ті поради і був упевнений, що гетьман подає їх з міркувань відданості російським інтересам. У 1705 і 1706 роках Мазепа ходив з військом у польські володіння, не зробив там нічого важливого, але скористався нагодою ще прихилити до себе царя, запропонувавши йому в дарунок 1000 коней, якраз тоді, коли вони Петрові особливо були потрібні для війська. У 1707 році цар наказав Мазепі повернутися з Польщі.
Важко було кому-небудь настроїти царя проти улюбленого гетьмана. За вкоріненою серед малорусів схильністю до доносів, багато було бажаючих зладувати Мазепі шлях Многогрішного й Самойловича. Але з остраху за власну голову мало знаходилося охочих поткнутися з доносом до царя, який так вірив гетьманові. У 1699 р. надумався було бунчуковий товариш Данило Забіла, спираючись на заступництво боярина Бориса Петровича Шереметева (18), з'явитися до Москви звинувачувати Мазепу в таємних зносинах з ханом; справа скінчилася тим, що донощика самого відправили до Батурина Мазепі: там Забіла постав перед генеральним судом і під тортурами засвідчив, що говорив про гетьманську зраду в п'яному стані без розуму й пам'яті. Його Присудили до смертної кари, але Мазепа подарував йому життя, замінивши смертну кару тяжким довічним ув'язненням. У 1705 році Мазепа одержав нагоду навести Петрові безсумнівний доказ своєї вірності. Обраний Карлом XII (19) на польського короля Станіслав Лещинський (20) спробував було підіслати до Мазепи якогось Вольського з намовляннями – схилити гетьмана на свій бік. Але Мазепа переслав лист Станіслава цареві і скаржився, що вороги ображають його, вважаючи здатним на зраду своєму владареві. Після цієї події ще важче стало будь-кому відважитися на донос, поки в 1707 році не знайшовся новий донощик на Мазепу: то був один із членів генеральної старшини, генеральний суддя Василь Леонтійович Кочубей.
Між гетьманом і Кочубеєм існувала сімейна ворожнеча. Кочубей мав дві дочки: одна – Ганна, котра вийшла за Мазепиного небожа Обідовського і невдовзі овдовіла, друга – Мотрона, Мазепина хрещениця. Мазепа, будучи вдівцем, надумав свататися до Мотрони. Батьки заперечили проти такого шлюбу, котрий ні в якому разі не міг бути дозволеним за церковними правилами. Мати Мотронина, жінка гордовита й сварлива, почала після того поводитися суворо із своєю дочкою і довела її до того, що їй стало незмога жити в батьківському домі, в Батурині, де її батько мусив постійно мешкати відповідно до звання генерального судді. Мотрона втекла до гетьмана. Мазепа, не бажаючи ославити дівчину, відіслав її назад до батьків, хоч писав їй потім: «Нікого ще на світі я так не кохав, як вас, і для мене було б щастя й радість, якби ви приїхали і жили б у мене, але я усвідомив, який кінець з того може вийти, особливо за такої злоби і єхидства ваших рідних: прийшло б од церкви неблагословення, щоб разом не жити, і де б я тоді вас подів. Мені вас було шкода, щоб ви потім на мене не плакалися». Але становище поверненої до батьківського дому Мотрони стало ще гіршим: мати мучила її жорстоким поводженням; батько, перебуваючи під сильним впливом дружини, чинив у всьому так, як вона хотіла. Батьки Мотронині скаржилися серед своїх знайомих, що гетьман звабив їхню дочку й знеславив їхню сім'ю. Мотрона таємно переписувалася з Мазепою, скаржилася на матір, називаючи її мучителькою. Мазепа втішав її, запевняв у своїй любові, але радив їй на крайній випадок іти в монастир. Кочубей писав Мазепі докори, а Мазепа відповідав йому: «Ти згадуєш про якийсь блуд, я не знаю і не розумію нічого, сам ти, видать, блудиш, слухаючи своєї гордовитої, язикатої жінки, котру, як бачу, не вмієш стримувати. Справедлива приказка: де всім правує хвіст, там напевне голова блудить. Жона твоя, а не хтось інший причина твоєї домашньої печалі-Свята Варвара втікала від свого батька, та не в гетьманський дім, а до пастухів у кам'яні ущелини».
За намовою жінки своєї Кочубей дошукувався можливості в той чи інший спосіб заподіяти гетьманові зло і дійшов думки: скласти донос і звинуватити гетьмана в зраді. Спочатку посередником для пересилання доносу він обрав якогось великоруського ченця, котрий тинявся і старцював по Малоросії-Його прийняли у Кочубея в Батурині, нагодували, обдарували, і він вислухав од Кочубея та його дружини жалісливу розповідь про те, як гетьман, закликавши до себе в гості доньку Кочубеєву, свою хрещеницю, зґвалтував ft Коли цей монах відвідав Кочубеїв удруге, подружжя спершу примусило монаха цілувати хрест на тому, що буде він берегти в таємниці те, що почує від них, потім Кочубей сказав: «Гетьман хоче відкинутися від Москви і пристати до ляхів; ступай у Москву і донеси про це бояринові Мусіну-Пушкіну» (21). Монах виконав доручення. Монаха допитали в Преображенському приказі (22), але ніякої справи про зраду малоросійського гетьмана не розпочинали. Минуло кілька місяців. Кочубей, побачивши, що спроба не вдалася, почав шукати інших шляхів: вони зголосилися з колишнім полтавським полковником Іскрою, свояком Кочубея. Не зважуючись самому починати справу, Іскра прислужився Кочубеєві лише тим, що відправив полтавського попа Спаської церкви, Івана Святайла, до свого приятеля, охтирського полковника Федора Осипова, просити у нього побачення з приводу важливої державної справи. Охтирський полковник з'їхався з Іскрою на своїй пасіці. «Я чув од Кочубея, – сказав йому Іскра, – що Мазепа, зв'язавшись із Лещинським, має намір зрадити Цареві і навіть замірявся на життя цареве, гадаючи, що цар приїде до нього в Батурин».