Безбородко забрал Виктора и его старшего брата Аполлона в Петербург, записал в гвардию и поместил племянников в пансион Де Вильнева, в те времена — одно из лучших учебных заведений в столице.
В 1784 г. Кочубей назначается адъютантом к князю Потемкину и причислен к российской миссии в Швеции, где слушал лекции в Упсальском университете. В частности, темой этих лекций — естественное право — неотъемлемые права, которые принадлежат ему исходя из самого факта его принадлежности к человеческому роду. В конспектах Виктора Павловича сохранились записи, касающиеся «прав народов». К этому нужно добавить, что Швеция в те времена стояла наряду с Англией, одним из образцов конституционной монархии, шведские законы и устройство государства в свое время произвели большое впечатление на Н.И. Панина.
Получив опыт дипломатической работы под началом своего дяди, в 1786 г. Кочубей вместе с братом произведен в камер-юнкеры, попал в свиту Екатерины, во время ее поездки в Крым.
В 1786 г. Кочубей тайно вступил в масонскую ложу Минервы, а весной 1788 г. причислен к лондонской миссии, с правом путешествовать по Европе для окончания образования. В Англии Кочубей познакомился с братьями Воронцовыми и произвел на них хорошее впечатление, что самым наилучшим образом сказалось на его дальнейшей карьере.
Учился в Париже, где прослушал курс истории литературы у Жана-Франсуа де Лагарпа, ярого республиканца и близкого друга Вольтера. Лагарп «спрятал» внутри своего курса рассказы о работах Вольтера и Монтескьё, о сравнении последним монархического и республиканского правления и, судя по конспектам Кочубея, они не прошли мимо его внимания.
Отлучившись на короткое время из Парижа, Кочубей побывал в Швейцарии — классической европейской республике, о которой Екатерина в свое время писала Павлу Петровичу и Марии Федоровне: «Я довольна, что вы видели этих республиканцев у них дома».
В 1792 г. его вызывают в Петербург и отправляют чрезвычайным посланником в Турцию. В российской столице Виктор Павлович произвел очень хорошее впечатление, как своими познаниями, так и парижским светским лоском. Он сумел понравиться всем — и молодому фавориту Екатерины II Платону Зубову, и ненавидевшему Зубова Павлу Петровичу (перед самым отъездом к месту нового служения Кочубей по приглашению наследника провел у него два дня в Гатчине) — и великому князю Александру. Тот писал ему в Константинополь очень дружеские и откровенные письма, настаивал, чтобы Кочубей в обращениях к нему как можно реже употреблял его титул, рассказывал о первой встрече с невестой, и главное — о том, как недоволен он всем происходящим при Дворе бабушки и готов отказаться от престола, как только он к нему перейдет. Тогда-то, видимо, Кочубей и подал ему мысль, что Александр должен не отрекаться от престола, а воспользоваться своим положением для того, чтобы реформировать Россию.