Тогда Мазепа, по царскому приказанию, выступил на правую сторону Днепра, как бы следуя против шведов, и начал звать к себе казацких начальников. Явился к нему Самусь и положил перед ним свои гетманские знаки. Явился и Палий, надеявшийся, что теперь, наконец-то, русский царь примет его в подданство и исполнится давнее его желание. Мазепа задержал Палия в своем лагере, по-видимому, дружелюбно, а между тем сносился с Головиным и спрашивал, что следует делать с Палием, который, как доносил Мазепа, пребывая в гетманском лагере, постоянно пьянствовал. Головин приказал предложить Палию ехать в Москву, а если он откажется, то узнать – не расположен ли он к врагам России, и, в случае улик в таком расположении, арестовать его. Обличители Палия тотчас нашлись: какой-то хвастовский иудей показал, что Палий сносился с гетманом Любомирским, принявшим тогда сторону Карла XII, и Любомирский обещал Палию прислать денег от шведского короля. Показания арендатора-еврея подтвердил священник Гриц Карасевич. Мазепа, простоявши несколько дней лагерем в местечке Паволочи, в конце июля 1704 года перешел в Бердичев и там, пригласивши к себе Палия, напоил его допьяна, потом приказал заковать и отправил в Батурин, где караульные сдали Палия, вместе с его пасынком, русским властям. По царскому приказанию его отправили на вечную ссылку в Енисейск.

Так, в согласии с русским правительством расправлялся Мазепа с народными элементами в южной Руси, враждебными польско-шляхетскому направлению. Русский государь все более и более благоволил к Мазепе и считал его единственным из всех бывших малороссийских гетманов, на которого смело могло положиться русское правительство. Во время взятия Азова, Мазепа охранял у Коломака русские границы от татар, а пятнадцать тысяч его казаков, под начальством черниговского полковника Лизогуба, отличались под Азовом. За это более всех награжден был царем сам Мазепа. Еще в 1696 году, после взятия Азова, царь виделся с ним в полковом городе слободских полков Острогожске и получил от него в подарок турецкую саблю с драгоценною оправою и щит на золотой цепи, а гетмана отдарил шелковыми материями и собольими мехами. В 1700 году государь сделал Мазепу кавалером учрежденного ордена Андрея Первозванного. В 1703 году Петр подарил ему Крупицкую волость в Севском уезде. В шведской войне участвовали казаки без Мазепы, под предводительством других начальников, а царскую признательность за их подвиги получал малороссийский гетман. Стараясь более подделаться в милость к государю, Мазепа в своих донесениях то и дело жаловался на беспокойный дух подчиненных себе малоруссов, особенно бранил запорожцев. В одном только расходился гетман с царем: гетман постоянно считал возможным и полезным возвратить в подданство России, уступленную Польше, правобережную Малороссию; Петр не поддавался таким советам, не желал ссориться с Польшею, но не сердился и на Мазепу за его советы, будучи уверен, что гетман дает их от преданности русским интересам. В 1705 и 1706 годах Мазепа ходил с войском в польские пределы, не сделал там ничего важного, но имел еще случай расположить к себе царя, предложивши ему в дар 1000 лошадей, именно в то время, когда Петр нуждался в них для войска. В 1707 году царь велел Мазепе возвратиться из Польши.

Трудно было кому-нибудь вооружать царя против любимого гетмана. По укоренившейся у малоруссов охоте к доносам, много было желавших подготовить Мазепе путь Многогрешного и Самойловича. Но из боязни за собственную голову, мало находилось охотников сунуться с доносом к царю, который так верил гетману. В 1699 г. вздумал было бунчуковый товарищ Данило Забела, опираясь на покровительство боярина Бориса Петровича Шереметева, явиться в Москву обвинять Мазепу в тайных сношениях с ханом; дело кончилось тем, что доносителя самого отправили в Батурин к Мазепе: там Забела предан был генеральному суду и под пыткой показал, что говорил о гетманской измене в пьяном виде без разума и памяти. Его приговорили к смертной казни, но Мазепа даровал ему жизнь, заменивши смертную казнь тяжелым пожизненным заключением. В 1705 году Мазепа имел случай показать Петру несомненный довод своей верности. Избранный Карлом XII в польские короли, Станислав Лещинский попытался было отправить к Мазепе какого-то Вольского с подущениями – склонить гетмана на свою сторону. Но Мазепа прислал письмо Станислава к царю и жаловался, что враги оскорбляют его, считая способным к измене своему государю. После этого события еще труднее было кому-нибудь отважиться на донос, пока в 1707 году нашелся новый доноситель на Мазепу: то был один из членов генеральной старшины, генеральный судья Василий Леонтьевич Кочубей.

Между гетманом и Кочубеем существовала семейная вражда. У Кочубея было две дочери: одна – Анна, вышедшая за Мазепина племянника Обидовского и скоро овдовевшая, другая – Матрена, Мазепина крестница. Мазепа, будучи вдовцом, вздумал сделать предложение Матрене. Родители воспротивились такому браку, который ни в каком случае не мог быть дозволительным по церковным правилам. Мать Матрены, женщина гордая и вздорная, начала после того обращаться сурово со своей дочерью и довела ее до того, что ей не стало терпения жить в родительском доме, находившемся в Батурине, где ее отец должен был постоянно проживать по званию генерального судьи. Матрена убежала к гетману. Мазепа, не желая срамить девушку, отослал ее обратно к родителям, хотя писал ей потом: «Никого еще на свете я так не любил, как вас, и для меня было бы счастье и радость, если бы вы приехали и жили бы у меня, но я сообразил, какой конец из того может выйти, особенно при такой злобе и ехидстве ваших родных: пришло бы от церкви неблагословение, чтоб вместе не жить, и где бы я тогда вас дел. Мне вас было жаль, чтоб вы потом на меня не плакали». Но положение возвращенной в родительский дом Матрены стало еще хуже: мать мучила ее жестоким обращением; отец, находясь под сильным влиянием жены, поступал во всем так, как она хотела. Родители Матрены жаловались в кругу своих знакомых, что гетман обольстил их дочь и обесславил их семью. Матрена тайно переписывалась с Мазепой, жаловалась на мать, называя ее мучительницей. Мазепа утешал ее, уверял в своей любви, но советовал ей в крайнем случае идти в монастырь. Кочубей писал к Мазепе упреки, а Мазепа отвечал ему: «Ты упоминаешь о каком-то блуде; я не знаю и не понимаю ничего; сам ты, видно, блудишь, слушаясь своей гордой, болтливой жены, которую, как вижу, не умеешь сдерживать. Справедлива народная пословица: где всем правит хвост, там, наверно, голова блудит. Жена твоя, а не кто другой причиной твоей домашней печали. Святая Варвара убегала от своего отца, да и не в гетманский дом, а к пастухам в каменные расщелины».

По наущению жены своей, Кочубей искал возможности тем или другим способом сделать гетману зло и пришел к мысли: составить донос и обвинить гетмана в измене. Сначала посредником для представления доноса выбран был какой-то великорусский монах из Севска, шатавшийся за милостыней по Малороссии. Он был принят у Кочубея в Батурине, накормлен, одарен, и выслушал от Кочубея и от его жены жалобный рассказ о том, как гетман, зазвавши к себе в гости дочь Кочубея, свою крестницу, изнасиловал ее. Когда этот монах посетил Кочубеев в другой раз, супруги сперва заставили монаха целовать крест в том, что будет хранить в тайне то, что услышит от них, потом Кочубей сказал: «Гетман хочет отложиться от Москвы и пристать к ляхам; ступай в Москву и донеси об этом боярину Мусину-Пушкину». Монах исполнил поручение. Монаха допросили в Преображенском приказе, но никакого дела об измене малороссийского гетмана не начинали. Прошло несколько месяцев. Кочубеи, видя, что попытка не удалась, стали искать других путей; они согласились с бывшим полтавским полковником Искрой, свояком Кочубея. Не решаясь сам начинать дело, Искра услужил Кочубею только тем, что отправил полтавского попа Спасской церкви, Ивана Святайла, к своему приятелю, ахтырскому полковнику Федору Осипову, просить у него свидания по важному государеву делу. Ахтырский полковник съехался с Искрой в своей пасеке. «Я слышал от Кочубея, – сказал ему Искра, – что Мазепа, соединившись с Лещинским, намерен изменить царю и даже злоумышлял на жизнь государя, думая, что государь приедет к нему в Батурин».