Скоро, однако, шведское правительство изменит своё мнение и станет рассматривать русские гарантии конституционного строя как вмешательство во внутренние дела государства.
Добиться от шведов признания императорского титула Петра I и титула «королевское высочество» для герцога Карла-Фридриха было более лёгкой задачей, нежели отвращение Швеции от Ганноверского союза. Тем не менее, посланник, можно сказать, превзошёл самого себя и 22 февраля 1724 года успешно завершил переговоры со шведским правительством, подписав т. н. Стокгольмский союзный договор. Пётр наградил посланника званием действительного камергера, наделил его полномочиями чрезвычайного посланника и увеличил жалованье до 5.000 рублей в год.
Согласно шведу Г. Веттербергу, курс на заключение со Швецией оборонительного союза Пётр I сформулировал в июле 1723 года. Царь проинструктировал Бестужева, чтобы в договор об этом союзе вошёл пункт о том, чтобы риксдаг не признавал иного наследника трона, кроме голштинского герцога. Ещё в 1718 году, во время переговоров со шведами на Аландских островах, Петру стало ясно, что Европа не смирится просто так с победой России в Северной войне и примет свои меры. Поэтому Пётр заранее хотел в лице Швеции заручиться надёжным союзником.
Переговоры о союзе проходили между Бестужевым и Хорном в обстановке строгой секретности: ни риксрод (госсовет), ни король в них посвящены не были. В качестве связных между Хорном и Бестужевым выступали «голштинцы» госсоветник Юсиас Седеръельм и статс-секретарь по иностранным делам Даниэль Никлас Хёпкен. Спорным пунктом в переговорах, как и ожидалось, явилось русское предложение относительно Карла Фредрика. В конце августа Хёпкен и Седеръельм вместе с Хорном выработали свой проект договора, в котором упоминаний о голштинском герцоге не было, и отправили его на рассмотрение царя в Петербург.
И только после этого Бестужев официально передал шведам предложение о заключении договора. В документе содержался лишь один вопрос: готово ли шведское правительство вступить в переговоры о заключении оборонительного альянса? В положительном случае посланник должен был запросить подробные инструкции и приступить к делу. В этот же день Хёпкен проинформировал о полученном русском предложении секретную комиссию. Т.н. малая секретная депутация самый узкий круг лиц из числа секретной комиссии, посвящённых в серьёзные государственные дела отреагировала на это мгновенно: союз с Россией был «неизбежным, выгодным и не авантюрным». Формулировка принадлежала «голштинцу» барону Ю. Седеръельму. 27 сентября госсовет, после обмена репликами между Хорном и королём, тоже одобрил идею союза. Оставалось договориться лишь об условиях союза.
Неудобный пункт о голштинском герцоге был «перекинут» Хорном на решение коллегии канцелярии. 10 октября коллегия вынесла соломоново решение: Карл-Фридрих мог питать «близкую надежду на участие в вопросе о престолонаследии». После этого эту формулировку шлифовала малая секретная депутация, т.е. практически Хорн, Седеръельм и Хёпкен, а потом она обсуждалась госсоветом вместе с секретным комитетом риксдага. После долгих дискуссий родилась ещё более аморфная формулировка о возможности при соответствующих обстоятельствах рассмотреть вопрос о голштинском принце как наследнике шведского трона. Бестужеву всё стало ясно, ломать копья было бессмысленно важнее было спасти сам договор. Удовлетворился результатом и Бассевич. 19 ноября 1723 года был опубликован соответствующий манифест, и вопрос о Карле Фридрихе с повестки дня переговоров был снят.
На заключительной стадии переговоров Пётр I сообщил шведам, что он в принципе согласен на брак своей дочери с Карлом-Фридрихом и приступил к коронации своей супруги Екатерины. Судьба императрицы и голштинского герцога теперь тесно были увязаны в один узел, пишет Веттерберг. Для шведско-русских отношений, продолжает историк, интересы Карла-Фридриха и возвращение ему Шлезвига стали головной болью. Но включение Шлезвига в состав Дании было гарантировано Англией, а ссориться с этой великой морской державой в планы А. Хорна не входило.
И снова Хорн предложил передать голштинский вопрос на рассмотрение других заинтересованных держав Австрии, Франции и Англии, и русская сторона была вынуждена с этим согласиться. Далее Хорн потребовал, чтобы оборонительные обязательства Швеции и России распространялись только на конфликты христианских держав, что освобождало шведов от оказания помощи России в её войнах с Турцией и Персией. Шведы захотели также включить в текст договора пункт о возвращении всех задержанных в России военнопленных каролинов, в частности тех из них, кто принял православие, на что Бестужев ответил, что царь Пётр уже принял необходимые для этого меры.
Проблемы в связи с репатриацией шведских военнопленных из России действительно были. Российские власти не сумели хорошенько подготовиться к решению этой проблемы: плохо был поставлен учёт военнопленных, не хватало денежных и других средств на сборы и продовольствие, ощущался недостаток гужевого транспорта на отправку пленных к местам концентрации репатриационных партий в Москве и Санкт-Петербурге, а помещики неохотно расставались с дешёвой квалифицированной рабочей силой и утаивали пленных от репатриации. Присланный Стокгольмом комиссар барон Й. Седеркройц и шведский резидент Томас Книпперкруна7 в своих жалобах российским властям постоянно напоминали о препятствиях на пути возвращения пленных на родину. 18 ноября 1723 года Бестужев доложил в Санкт-Петербург о гневной реакции шведских министров, а 20 января 1724 года Пётр издал грозный приказ о наведении в репатриационных деах надлежащего порядка.
23 февраля 1724 года договор был подписан. Он был рассчитан на 12 лет и являлся первым союзным договором, заключённым Швецией после Ништадтского мира. Стороны гарантировали друг друга от агрессии какой-либо европейской державы и намеревались выставить против агрессора вспомогательный корпус, в который Россия предоставляла 12 тысяч солдат и 4 тысяч драгун и эскадру в составе 9 русских линейных кораблей, а Швеция 8 тысяч пехотинцев, 2 тысячи кавалеристов и эскадру численностью в 6 шведских линейных кораблей и 2 фрегатов. Союз гарантировал неизменность конституции Польши, декларировал восстановление суверенитета герцога Готторп-Голштинии в Шлезвиге и предоставлял шведским купцам некоторые привилегии в России. В споре за суверенитет Готторп-Голштинского герцогства стороны, как было указано выше, должны были советоваться с другими державами, в первую очередь с Австрией и Англией.
Конечно, Стокгольмский союзный оборонительный договор представлял собой слабое воплощение идеи Петра о превращении шведского противника в надёжного союзника. Искреннего союза между бывшими противниками, к сожалению, не получилось. А. Хорн постарался не брать слишком больших обязательств по отношению к России. Швеция стремилась к союзу то с Англией, то с Францией, то с Пруссией или Турцией, и договор был для России лишь слабым поводком на шее Швеции, готовым порваться в любую минуту. Тем не менее, некоторое время Хорн по внутриполитическим соображениям считал для себя и новой власти полезным опираться на Россию и голштинскую партию в противовес королю Фредрику, делавшему ставку на Гессен и Англию, но это период был очень коротким.