В это время в Вене появился опытный дипломат Петр Андреевич Толстой с посланием царя к императору Карлу. Прибытие Толстого в Вену было подобно грому среди ясного неба – император и его министры были абсолютно уверены, что им удалось упрятать царевича так основательно, что его никто не сможет обнаружить. В послании царь без обиняков выразил «любезному другу и брату» свое удивление по поводу того, что его сына укрывали в Эренберге, а теперь отправляют в Неаполь.
Руководство операцией по возвращению беглеца в Россию царь поручил Толстому. Сразу можно сказать, что лучшего исполнителя повеления царя трудно было сыскать, ибо Толстой являлся искусным дипломатом и прекрасно владел диаметрально противоположными приемами ведения переговоров: он сочетал ласку и лесть с жесткостью и даже жестокостью, не останавливаясь перед тем, чтобы лишить жизни человека, если в том возникала необходимость. (Будучи послом в Турции, Толстой собственноручно отравил одного подьячего из состава посольства, принявшего ислам, опасаясь, что тот может раскрыть туркам шпионскую сеть, умело организованную им в столице Османской империи.) Кроме того, Петр Андреевич обладал еще двумя очень важными в данном случае преимуществами: он хорошо знал итальянский язык и уже бывал в Неаполе, где скрывался царевич.
Толстой не ограничился аудиенцией у императора. Он вступил в переговоры с его тещей герцогиней Вольфенбюттельской, бывшей одновременно матерью покойной супруги царевича Алексея Шарлотты Христины Софьи. Хотя теща царевича поначалу заявила, что ей неведомо место его пребывания, но затем под напором фактов вынуждена была дать обещание всячески содействовать возвращению беглеца. Пришлось идти на уступки и императору. Австрийское правительство признало факт предоставления убежища царевичу Алексею. Толстому разрешено было встретиться с ним. Правда, ему было заявлено, что если царевич откажется вернуться в Россию, то насильно, вопреки его воле, выдавать его не будут.
Но все же это был несомненный успех Толстого. Открывались пути непосредственного воздействия на царевича.
Прежде всего Толстой добился права на свидания с царевичем у неаполитанских властей. Более того, император отправил в Неаполь курьера с повелением вице-королю графу Дауну оказывать всяческую помощь Толстому.