Биография В. П. Кочубея была бы неполной, если не вспомнить отношения его с Пушкиным. А тут конфликт был куда более непримиримый, чем с Павлом или Александром, и лишь немного недотягивал до конфликта его прадеда с Мазепой.
Встреча Наталии Викторовны Кочубей с Александром Сергеевичем Пушкиным относится к первым годам его учёбы в Лицее. Проводя летние месяцы вместе с родителями на даче в Царском Селе, юная графиня часто встречалась с лицеистами.
Позднее в набросках к автобиографии под периодом «1813 год» Пушкин запишет: «Гр. Кочубей». По мнению М. А. Корфа, «едва ли не она (а не Бакунина) была первым предметом любви Пушкина». Возможно, ей посвящены стихотворения «Измены» (1815) и «Воспоминаньем упоенный» (1819).
П. К. Губер в своей книге «Донжуанский список А. С. Пушкина» (1923) выдвигал такую гипотезу расшифровки инициалов «NN» (не получившую, правда, никакой поддержки): «…Пушкин нашёл в своём чувстве кН. В. Кочубей-Строгановой новый, обильный источник поэтического возбуждения, не иссякавший до 1828 г. С воспоминаниями о Наталии Викторовне, кроме «Полтавы», можно связать «Кавказского Пленника», «Бахчисарайский Фонтан», «Разговор книгопродавца с поэтом», некоторые лирические строфы «Евгения Онегина» и, наконец, по собственному признанию Пушкина, кое-какие штрихи в характере Татьяны».
Кочубей не видел в Пушкине своего зятя и выдал дочь замуж за Александра Григорьевича Строганова, троюродного брата будущей супруги поэта. Поэт не остался в долгу и в 1830 году в стихотворении «Моя родословная» припомнил дядюшку Виктора Павловича: «В князья не прыгал из хохлов». Год спустя в князья «прыгнет из хохлов» и сам Кочубей.
Первый бал, который Пушкин посетил вместе с молодой супругой, состоялся в особняке Кочубея. Там присутствовала и дочь хозяина вместе с мужем, который в октябре 1831 года был произведён в чин генерал-майора и назначен в свиту Его Величества. В первой половине ноября в восьмой главе «Евгения Онегина» появляются строки, в которых, по мнению П. В. Плетнёва, поэт описал именно графиню Наталию Викторовну:
К хозяйке дама приближалась,
За нею важный генерал.
Позднее именно она всячески старалась предотвратить дуэль Пушкина с Дантесом. И это притом что на смерть её отца поэт отреагировал так: «Царь был неутешен, новые министры повесили головы». И добавил ходившую в те дни в списках эпитафию (не свою):
Под камнем сим лежит граф Виктор Кочубей.
Что в жизни доброго он сделал для людей,
Не знаю, черт меня убей.
И это после выхода гоголевских «Вечеров на хуторе близ Диканьки» и его собственной «Полтавы»!