В противостоянии с турками и шведами Россия не была одинокой. С Турцией имели свои счеты Польша, Австрия и Венеция, особенно первая, и это обстоятельство делало их естественными союзниками России. Точно также и Швеция восстановила против себя своих соседей Польшу, Данию и Бранденбург, грозя превратить Балтийское море, как тогда говорили, в «Варяжское озеро», то есть завладеть всеми его берегами. Отсюда — сложная система союзов, в которой свое место заняла и Россия.
В марте 1686 года прибыли в Москву для заключения союза против турок польские послы. Вести переговоры, или, по-тогдашнему, «быть в ответе», был назначен с русской стороны среди других и Б. П. Шереметев. С самого начала русские выставили непременным условием заключения союза закрепление Киева, уступленного полякам в 1667 году, за Москвой, а взамен этого обязывались разорвать мир с султаном и двинуть войска в Крым. Поляки упорно хотели сохранить Киев за собой, и только крайняя нужда в таком мощном союзнике, как Москва, заставила их согласиться на русские условия. Эта большая победа московской дипломатии лично Шереметеву принесла звание «ближнего боярина и наместника Вятского». Он же был отправлен в конце 1686 года в Польшу во главе огромного посольства, а затем с тем же посольством — в Вену, чтобы объявить императору Леопольду о заключении «вечного мира» с поляками.
При исполнении этих поручений Борис Петрович проявлял обычные московским дипломатам свойства — не знающую колебаний стойкость в преследовании поставленной задачи и неумолимую требовательность в отношении посольского церемониала. В возникавших не раз в Польше и Австрии на этой почве спорах — например, по вопросу о том, в каком месте выходить из кареты при приезде ко дворцу, когда снимать шапку, как произносить царский титул, сколько раз кланяться и т. п. — обыкновенно верх оставался за московским боярином. А наряду с этим в поведении Шереметева сказались, как мы уже видели, и новые, незнакомые дипломатам прежнего времени черты, свидетельствовавшие о зарождении в Москве новой культуры поведения.
Дипломатические поручения были, однако, только эпизодами в жизни Бориса Петровича. Поприщем, на котором он приобрел известность, было военное дело. Вскоре по возвращении из посольства он был назначен воеводой Белгородского разряда, на обязанности которого лежала охрана южной границы от татарских набегов, а в следующем, 1688 году принял участие в походе В. В. Голицына против Крыма, предпринятом согласно условиям «вечного мира» с Польшей. Это первое выступление будущего фельдмаршала в настоящих сражениях не было, однако, удачным: в двух сражениях в Черной и Зеленой долинах предводительствуемый им отряд был смят татарами, хотя он сам и проявил большую храбрость.
В первое время по вступлении Петра в управление государством положение Шереметева не изменилось. Хотя он без колебаний стал на сторону Петра в столкновении его с сестрой-правительницей, тем не менее молодой царь не оставил его при себе, а послал на прежнюю должность в Белгород. Так, в течение почти восьми лет, до 1695 года, Борис Петрович оставался вдали от Москвы и царского двора, пока Петр, начиная войну с турками во исполнение все того же договора с Польшей, не призвал его. На этот раз ближайшей целью войны был Азов. По принятому на военном совете плану русские войска должны были действовать одновременно в двух направлениях: полки нового строя вместе с московскими стрельцами были двинуты к Азову, чтобы овладеть им, в то время как дворянская конница и казаки, направленные к низовьям Днепра, должны были отвлечь на себя крымских татар. Шереметеву ввиду его опыта борьбы с крымцами и турками поручено было командовать этой второй армией общей численностью до 120 тысяч человек.
Может быть, вспоминая печальные уроки крымских походов Голицына, Шереметев принял назначение с явной неохотой. И на самом деле задача была выполнена им только отчасти. В первый год войны после четырехдневной осады сдался ему хорошо укрепленный турецкий городок Кызы-Кермен на Днепре, после чего турки уже без боя отдали три других таких же городка. Но до Крыма Шереметев не дошел и вернулся на Украину. Следующий год дал еще меньше. Шереметеву велено было, соединившись с Мазепой, идти под Очаков, но он дошел до реки Берестовой и здесь остановился. Между тем почти все татарское войско было в это время на Дону, под Азовом, и только крайняя осторожность полководца помешала русским разгромить беззащитный Крым.