Начало второго этапа строительства (1698—1701) совпадает с возвращением Петра I из поездки по Европе в 1698 году. Царь повелел выстроить над воротами третий ярус — сюда вселилась по его указу в 1701 году «Школа математических и навигацких наук». А над всем сооружением поднялась высокая башня, отдаленно похожая на общественные здания европейских городов. Здание значительно выросло в высоту, достигнув 30 сажен (64 метра). К нему пристроили с востока знаменитое крыльцо в два лестничных марша. (По новейшим извысканиям, прослеживаются четыре строительных периода: башня последовательно подрастала в высоту, а палатные строения над воротами приобретали характер единого блока.) Архитектором Сухаревой башни источники единодушно называют М.И. Чоглокова (ум. в 1709 году), обучавшегося в Оружейной палате, впоследствии строителя Арсенала в Кремле.

Школа навигацких (мореходных) наук не случайно помещена была в Сухаревой башне: здесь, на вершине Сретенского холма (по мнению историков XIX века, одного из семи московских холмов), было одно из самых высоких мест города, что позволяло беспрепятственно видеть горизонт и вести астрономические и навигационные наблюдения. Шатер башни был в 100 метрах над уровнем Москвы-реки. По преданию, светлейший князь Меншиков выстроил свою башню на Чистых прудах такой высокой специально, чтобы затмить Сухареву Но честолюбивым замыслам Меншикова помешала молния. Ив начале XX века московские путеводители настоятельно советовали полюбоваться видами города с Сухаревой башни, «мало уступающими видам с Ивановской колокольни».

В навигацкой школе (в 1815 году переведена в Петербург, где из нее впоследствии выросла Морская академия) постигали «мореходных хитростно искусств учение» до 500 учеников 20—25 лет, в основном дети московских мелких чиновников, священнослужителей и солдат. Первыми преподавателями в ней были выписанные из Англии профессор Абердинского университета Эндрю Фарварсон, Стефан Гвын и Ричард Грейс (к слову сказать, в 1710 году убитый грабителями на московской улице на пути от Сухаревой башни домой, в Немецкую слободу). Позднее здесь преподавали такие известные русские ученые XVIII века, как Л. Магницкий и Я. Брюс.