В апреле 1699 года чрезвычайные посланники Украинцев и Чередеев отправились в Константинополь. Они ехали туда не с пустыми руками, повезли мехов на пять тысяч рублей, полтора пуда чаю, десять пудов рыбья зуба - на раздачу от государевых дел. Ехали на Воронеж, где были у государевой руки, с Воронежа водою до Азова, ехали мимо городов Костенска, Урыву, Коротояка и Дивьих гор; а за Коротояком по обеим сторонам Дона тринадцать вотчин, где городков, сел и деревень жилых нет, только юрты промышленных людей, наезжающих временно для рыбной и звериной ловли, человек по сороку, а владеют они по отдаче из оброку, нанимая у епископа воронежского и в монастырях. От этих вотчин вниз ехали мимо пятидесяти козачьих городков: когда равнялись с городком, выезжали навстречу станичные атаманы и козаки и для почтения в городках была пальба из пушек и мелкого ружья. Когда поровнялись с главным городом Черкасском, то посланники велели провожавшим их солдатам выстрелить первыми из ружей, и на этот выстрел отвечали пушки со всего города; посланники вышли из судов и пошли в соборную церковь, оттуда к атаману Фролу Минаеву; атаман отдал им визит на бударе. Из Черкасска поехали в Азов, из Азова в Таганрог, где в двух верстах от города дожидался их военный сорокашестипушечный корабль "Крепость", капитан голландец Петр фон Памбург. От Таганрога до Керчи посланники шли Азовским морем в государевом морском корабельном и галерном караване, над которым был предводителем и правителем ближний боярин и славного чина св. апостола Андрея кавалер и каравана воинского морского генерал-адмирал Федор Алексеевич Головин; командиром на корабле "Апостол Петр" был сам государь; в караване кроме "Крепости" было девять кораблей, две галеры, яхта, два галиота, три бригантира. В том же караване в четырех морских стругах шел донской атаман Фрол Минаев с пятьюстами выборных козаков.
Когда караван явился у Керчи, то здешний паша, видимо, испугался, спрашивал, зачем пришел такой большой караван, и присланный из Царя-града пристав настаивал, чтоб посланники ехали в Константинополь сухим путем, через Крым и Буджаки; но Украинцев отвечал: "По указу великого государя велено нам ехать морем на корабле царского величества, а сухим путем ехать нам не велено, да и не для чего, потому что тот путь в дальнем расстоянии; видно, ты, пристав, хочешь везти нас чрез Крым для какого-нибудь вымысла; только нам через Крым ехать не для чего, и до хана крымского никакого дела нам нет, говорить с ним не о чем". Пристав стращал посланников: "Видно, вы Черного моря не знаете, каково оно бывает с 15 августа, не напрасно дано ему имя Черное: бывают на нем во время нужды черны сердца человеческие". "Полагаемся на волю божию, а сухим путем не поедем", - отвечал Украинцев и закончил спор.
28 августа посланники вышли в море и благополучно достигли Царя-града; невиданное диво - русский корабль торжественно, при пушечной пальбе, вошел в Константинопольскую гавань и стал на якоре против сераля. Первым делом посланников было отправить капитана Памбурга с поздравлением к французскому, английскому и голландскому послам; француз и голландец приняли Памбурга любовно и за поздравление благодарили; англичанин же к себе не пустил, выслал на крыльцо человека и велел сказать, что видеться ему с Памбургом не для чего и сел он теперь за стол обедать. Начали приезжать смотреть диковину; приезжали французы из посольской свиты, приезжал великий визирь и долго ездил около корабля, хвалил и дивился, что корабль так скоро пришел из Керчи в Царь-град, наконец, приезжал сам султан.
Переговоры начались только в ноябре; посланники предложили статьи: 1) вечный мир или продолжительное перемирие с тем, чтоб каждая сторона удержала то, чем владела в минуту переговоров, следовательно, Россия удерживала за собою все завоевания. 2) Татары не должны тревожить Русские области. 3) Когда Азов, Казыкермень и другие крепости будут в русском владении, то своевольные люди обоих государств уймутся; эти крепости великий государь не для какой-нибудь себе славы в своей стороне держать изволяет, но только для унятия с обеих сторон своевольных людей. 4) Если во время мира козаки пойдут войною на турецкие и крымские места, то вольно их побивать, как злодеев; а когда и походу возвратятся, то по царскому указу учинена им будет смертная казнь; так же будет поступлено взаимно с турецкой и крымской стороны. 5) Дачу, которая прежде бывала крымскому хану и начальным людям, великий государь за многие их неправды велел отставить, и впредь им той дачи не будет. 6) Полон весь освобождается на условном месте разменою. 7) Свободная торговля с обеих сторон. 8) Запорожцам вольно промышлять зверем и рыбок вплоть до днепровского устья. 9) Порубежные ссоры успокоиваются чрез послов. 10) Русские люди свободно ходят на поклонение св. местам, не платя никаких податей. 11) Св. места возвращаются грекам. 12) Православные в турецких областях свободно отправляют свое богослужение.