Після 1702 року 63-річний гетьман залишився сам, не маючи прямих нащадків. Природно, що після смерті дружини гетьман-удівець мав право подумати про своє особисте життя і, насамперед, про спадкоємця. Адже рід Мазепи по його лінії міг обірватися. Слід відзначити, що Іван Степанович виглядав набагато молодшим від своїх років. Французький посол Жан де Балюз, який зустрічався з гетьманом у 1704 році в Батурині, так описує його: «Вигляд у нього суворий, очі блискучі, руки тонкі й білі, як у жінки, хоч тіло його міцніше, ніж тіло німецького рейтера, вершник з нього знаменитий».
Учасник шведського походу в Україну Густав Адлєрфельт побачив гетьмана «у віці 64-х літ, середнього зросту» (у 1708 році йому насправді було 69 років), він «дуже стрункий, із суворим поглядом, носить вуса на польську моду, приємної вдачі й дуже захоплює своїми жестами».
Невідомий шведський старшина у своїх нотатках про І. Мазепу зауважує, що «наші очі полонили його білі руки, тонкі, повні грації, та його горда голова з білими буклями, довгі обвислі вуса, а понад усім цим величність, почуття гідності й суворість, яку злагіднювала елеганція». Навіть у такому віці, як зізналася пані Сенявська французькому послу у Варшаві Францісу Бонаку, він «приваблює легко до себе своїм чаром жінок».
У 1704 році гетьман зробив свій вибір — його обраницею стала дочка генерального судді Василя Кочубея Мотря, якій на той час сповнилося років вісімнадцять-двадцять… Вікова різниця між ними була вражаючою. Однак ті, хто звинувачує Мазепу у блуді, не враховують одну суттєву деталь: гетьман домагався руки дівчини, яка відповідала йому взаємністю. Зрозуміти молоду Кочубеївну не важко: Іван Степанович для неї був, у першу чергу, уособленням мудрості, шанованою всіма людиною. Хрещений, який часто гостював у домі Кочубеїв, міг приворожити її і знанням мов, і власними віршами. Мова його листів до неї ніжна й зворушлива. «Щасливії мої письма, що в рученьках твоїх бувають, нежели мої бідніє очі, що тебе не оглядають», — писав він Мотрі.
Трагічно склалися взаємини юної Кочубеївни з гетьманом. Батьки дівчини, дізнавшись про намір І. Мазепи одружитись з їхньою дочкою, категорично відмовили йому.
Довідавшись про це, Мотря втекла у гетьманський палац. Мазепа, однак, змушений був відрядити її знову додому. У листі до коханої він пояснив свої дії так:
«Моє серденько! Зажурилемся, почувши од дівки таке слово, же В(аша) М(илість) за зле на мене маєш, іже В. М. при собі не задержалем, але одослал до дому. Уваж сама, що б з того виросло. Першая, що б твої родичі по всім світі розголосили: же взяв у нас дочку уночи гвалтом і держить у себе місто подложниці. Другая причина, же державши В. М. у себе, я бим не могл жадною мірою витримати, да і В. М. также: мусілибисьмо із собою жити так, як мал-женство каже, а потом прийшло би неблагословеніє од Церкви і клятва, жеби нам з собою не жити. Гді ж би я на тот час поділ. І мні б же чрез В. М. жаль, щоб єсь на потом на мене не плакала».
Та, незважаючи на шляхетність закоханого, однаково Кочубеї наробили у гетьманській столиці «гвалту». Любов Федорівна, мати Мотрі, звинувачувала гетьмана в тому, що він «знасиловал блудом» її дочку. Ці запальні емоційні висловлювання як достовірний факт стали використовувати супроти гетьмана чимало істориків. Так, П. Кропива у своїй розвідці зазначає, що І. Мазепа збезчестив дівчину, позбавивши її цноти. Насправді нічого подібного і ганебного не трапилося. Дочку Кочубеїв на прохання Мазепи повернув батькам російський полковник Григорій Анненков. Гетьман був високоморальною людиною, він не міг піти проти Бога і звичаїв. Як видно з його листів, плани для законного поєднання він передбачав. В одному з літописів ідеться про те, що Мазепа просив у «малороссийских архиереев и от греческих патриархов разрішення на брак». Але до цього не дійшло, оскільки, передусім, він не отримав батьківської згоди.