За рік по тому Лещинський зробив нову спробу, цього разу з більшим успіхом. Скориставшись умілим посередництвом княгині Анни Дольської, однієї з типових для тієї доби високородних інтриганок, польському королеві вдалося залучити гетьмана до обговорення конкретних пропозицій . Ця раптова зміна була великою мірою зумовлена успішним просуванням шведських військ, яке змушувало гетьмана розглядати можливість перемоги шведів дедалі поважніше. Сам Мазепа згодом пояснював близькому товаришеві, що він зважився на цей перший крок задля того, щоб Карл XII і Лещинський, "бачачи мою до себе прихильність, по-ворожому з нами не чинили і вогнем і мечем бідної України не спустошували" . Хоча в той час Мазепа ще діяв сам, не розкриваючи своїх планів, він обережно випробовував старшину щодо можливості порозуміння з "супротивною стороною". Майже всі головні урядовці цю ідею підтримали. Підбадьорений, але все ще тримаючи в таємниці від провідних діячів старшини свої контакти з Лещинським, Мазепа почав обговорювати з поляками умови, на яких він міг би перейти на їхній бік.
Оскільки переговори велися у великій таємниці й тому жодних документальних свідчень їхнього перебігу не залишилося, історикам довелося розшукувати розрізнені тогочасні матеріали, щоб з'ясувати позицію Мазепи в тому торзі. Від самого початку питання щодо планів, які виношував Мазепа, було сповнене суперечностей. Деякі сучасники твердили, що метою гетьмана було створення окремого українського князівства. Звертаючись до своїх офіцерів перед Полтавською битвою, Петро І заявив, що Карл XII і Лещинський прагнуть "відторгнути від Росії малоросійські народи та зробити князівство окремо під владою... Мазепи". Схожі твердження зустрічаються і в офіційному російському щоденнику подій 1708—1709рр. А один із Мазепиних полковників, Гнат Галаган, який лишився вірним цареві, згадував, що гетьман перейшов до ворога, "щоб відійти нам від Росії і бути під] Мазепиним управлінням, від усіх монархів вільним".і Петро І, а згодом і російські історики, щоб довести сута егоїстичні мотиви Мазепиного розриву з царем, наголошували, буцімто гетьман планував створити окреме князівство. Деякі українські історики також схилялися до думки, що метою Мазепи було створення окремого українського князівства, але їхнє тлумачення цього сепаратизму було зовсім іншим. Вони вбачали в цьому гетьманів патріотизм і бажання створити незалежну українську державу.
Більш поширене інше тлумачення, згідно з яким Мазепа мав здобути князівський титул, а Україна стала б третьою й рівноправною частиною польсько-литовської Речі Посполитої. Є чимало переконливих аргументів на користь цього тлумачення: таке розв'язання проблеми врегулювало б польсько-українські стосунки на користь обох сторін і не зачепило б соціально-економічних інтересів старшини; крім того, існував добре знаний прецедент Гадяцької угоди 1658 р.
Щойно про гетьманові зносини з Лещинським стало відомо, більшість сучасників також сприйняли їх як пошуки спілки України з Річчю Посполитою. Суперечачи власним твердженням, Петро І також звинувачував Мазепу в бажанні повернути українців у "польське рабство". Данило Апостол, один із провідних полковників і активних учасників змови, який згодом покаявся перед царем, розповідав, що гетьман "показав нам привілей короля Станіслава... Привілей той гарантував Україні вольності, як у Короні Польській та Великому Князівстві Литовському... Мазепі висловлено подяку за відгук той, який він писав до [польського] короля, піддаючи Україну під її владу, і всяких прав І вольностей, яких тільки могли б потребувати Україна і все Військо Запорозьке, нічого не відмовити обіцяно". Універсали щодо цього Лещинський таємно послав Мазепі 1707 р. для розгляду й розповсюдження в слушну годину. Це також спонукало полковників, на той час уже почасти поінформованих про переговори, зустрітися в Києві й таємно вивчити копію Гадяцької угоди, яку вони одержали з Печерської бібліотеки.
Чи уклав .Мазепа (або Лещинський), як твердять деякі історики, цю угоду з суто тактичних міркувань, не маючи наміру дотримуватися її по війні, ми ніколи не дізнаємося. Скажемо лише, що на той момент угода такого типу відповідала потребам обох сторін.
Порозуміння зі Станіславом проклало шлях Мазепиним контактам і з Карлом XII. У виданій після Полтавської битви відозві бажання гетьмана приєднатися до шведів описано як точне й пряме наслідування дій "хороброго гетьмана, славної пам'яті Богдана Хмельницького, який за допомогою... короля, Його Милості шведського, Карла Десятого... визволив з польського підданства військо Запорозьке і народ уярмлений і пригноблений малоросійський". Але цей Прецедент не був, звичайно, головною підставою прагнути безпосередніх контактів із Карлом XII. З огляду на панівне політичне й військове становище шведів, порозуміння з ними напевно мало б більше ваги, ніж із їхнім польським протеже. До того ж, усупереч обіцянкам короля та взаємним запевненням, і Лещинський, і Мазепа не повністю довіряли один одному. В цій ситуації схвалення Карлом XII угоди гетьмана з польським королем значно збільшило б імовірність того, що ця угода виконуватиметься. На початку контактів із Карлом XII Мазепа бачив його роль передусім як гаранта порозуміння, що його гетьман досяг із Лещинським.
Спочатку Карл XII не виказував великого інтересу до того, щоб стати таким гарантом, і навіть до налагодження зв'язків з українським гетьманом. Монарша солідарність утримувала молодого короля від зносин із васалом-дворушником. Але після того, як Лещинський уклав із гетьманом угоду, а шведи зіткнулися на півночі з великими труднощами, Карл XII поставився до Мазепиних пропозицій прихильніше.
Український історик Олександр Оглоблин запропонував досить оригінальне пояснення зростання інтересу шведів до Мазепи . Плани Карла XII полягали в тому, щоб позбавити трону Петра І, як це вже зроблено 1706р. з Августом II. Аби домогтися цього, шведський король потребував підтримки старої московської аристократії, відомої критичним ставленням до Петрового правління. Мазепа, пише Оглоблин, мав тісні зв'язки з цією аристократією, зокрема з боярином і фельдмаршалом Борисом Петровичем Шереметьєвим. Як уже згадувалося, саме він попередив гетьмана про махінації Меншикова та плани Петра І провести в Україні реформи. Співчуваючи Мазепі, Шереметьев якось зауважив: "Ми самі багато терпимо [від царя та Меншикова], але змушені мовчати". Можливо, саме ці настрої серед російських бояр спонукали прусського посла в Москві зазначити у своєму донесенні в січні 1709р., що цар "після несподіваного відступництва Мазепи почав сумніватись у вірності мало не всіх своїх бояр і князів".
Ще однією ланкою зв'язку гетьмана з традиціоналістськими критиками царя була його близька дружба з українськими церковниками, що посідали високі пости в Московщині, зокрема, митрополитом Ростовським Дмитром Тупталом, митрополитом Рязанським Стефаном Яворським й особливо з митрополитом Київським Йоасафом Кроковським, заарештованим згодом у зв'язку зі справою царевича Олексія. Хоча існує небагато конкретних свідчень дійсної співпраці між московськими й українськими захисниками старих порядків, ознаки на і кшталт тих, які вказав Оглоблин, наводять принаймні на думку, що вони симпатизували одні одним.
Серед істориків, що досліджували ці події, немає одностайності з приводу того, чи була до вступу шведів в Україну підписана офіційна угода між Мазепою та Карлом XII. Численні тогочасні джерела згадують якусь неофіційну домовленість між ними, у якій король пообіцяв зважати на українські інтереси. Єдине джерело, де чітко вказано на І існування такої угоди,— це документ під назвою "Вивід прав України" ("Deduction des droits de l'Ukraine"). Його опублікував 1925р. Ілько Борщак, відомий знавець того періоду, ідентифікувавши як меморандум, із яким 1712р. звернувся до європейських монархів Пилип Орлик. На думку дослідника, метою меморандуму було зміцнити претензії України на суверенітет. У ньому вміщено короткий виклад (із шести пунктів) угоди між Мазепою та Карлом XII, начебто підписаної 1708р. Пункти угоди такі: