Исполняя это поручение, Брюс доставлял близлежащую артиллерию к Ладоге, а 25 сентября за недостатком лошадей начал отправлять ее к Нотебургу (впоследствии Шлиссельбургу), куда уже шел сам Петр с 13-тысячной армией под командованием фельдмаршала Шереметева. Здесь, при осаде Нотебурга, Брюс, по утверждению Хмырова, впервые командовал всей артиллерией. Артиллерия Брюса при взятии Нотебурга состояла из девятнадцати пушек полковых фунтовых, двенадцати пушек калибром 12 фунтов и двенадцати мортир, которые были расположены на двух батареях и двух кетелях. В период с 1 по 11 октября по крепости было выпущено более шести тысяч ядер калибром от 18 до 6 фунтов и, более того, 2500 трехпудовых бомб, причем употреблено пороха 4371 пуд.
Старое русское название Нотебурга – Орешек. После взятия крепости Петр I писал в письме к Виниусу: «Правда, что зело жесток сей орех был, однако, слава Богу, счасливо разгрызен. Артиллерия наша зело чудесно дело свое исправила».
После взятия Нотебурга Брюс возвратился в Новгород. Зимой 1702/03 года он дружески сошелся с генерал-фельдмаршалом Б.П. Шереметевым, который стоял с армией на зимних квартирах близ Пскова и Ладоги и часто выезжал к своему новгородскому соседу. Дружба соединила этих сподвижников царя неслучайно. Оба они обладали наибольшими талантами в ряду близких царю людей и были очень порядочными и достойными военными.
Борис Петрович Шереметев был единственным военачальником, заявившем герцогу Кроа, что диспозиция русских войск перед сражением с отрядом Карла XII под Нарвой 19 ноября 1700 года была в корне неверной. Поражение это было предсказано блестящим полководцем, но сам он был объявлен едва ли не главным виновником этого поражения. Полководческий талант Шереметева был оценен уже в 1701 году при взятии Лифляндии. За боевые успехи Борис Петрович произведен в генерал-фельдмаршалы и награжден высшей наградой России – орденом Святого апостола Андрея Первозванного.
Как уже отмечалось, в этих походах Шереметева Я.В. Брюс, исполнявший обязанности «подручного начальника артиллерии», принимал участие и был в подчинении Бориса Петровича. Теперь, в 1702 году, отношения начальника и подчиненного перерастают в дружеские, и в дальнейшем оба генерала постоянно поддерживают их.
В марте 1703 года Б.П. Шереметев в письме Петру сообщает о своей дружбе с Яковом Брюсом: «…про здоровье мое извольте выпить, а про ваше здоровье обещаюся быть шумен и обедать днесь стану у Якова Вилимовича».