В конце XVII века у Сретенских ворот был расположен стрелецкий полк стольника Лаврентия Панкратьева Сухарева, по имени которого и назывался в это время Сухаревским полком [8]. Во время борьбы за престол Петра I с его сестрой, царевной Софьей, этот полк оставался неизменно верным Петру. Когда тот, спасаясь от козней сестры, убежал в 1689 году в Троице-Сергиеву лавру, полк последовал за ним — и охранял его до самого низложения Софьи и заточения в монастырь. Вероятно, в благодарность за верную службу Петр I и построил в 1692–1695 годах на месте деревянных Сретенских ворот, охранявшихся Сухаревским полком, двухэтажную палату, с проездными воротами посередине и трехъярусной башней с часами над вторым этажом
Доски были сделаны из мрамора, весили около 20 пудов и провисели над проездом под башней со стороны Сретенки 230 лет. В 1925 году были обнаружены на них трещины, вследствие чего они были сняты и заменены новыми, во всем им тождественными. Надпись на них, как и на старых, сделанная славянскими буквами, гласит следующее: 1) на левой меньшей доске: «Повелением благочестивейших, тишайших, самодержавнейших государей, царей и великих князей Иоанна Алексеевича, Петра Алексеевича всея великий и малыя и белыя России самодержцев, по стрелецкому приказу, при сиденье в том приказе Ивана Борисовича Троекурова»; 2) на правой большой доске: «Построены во втором Стрелецком полку по Земляному городу Сретенские ворота, а над теми вороты палаты и шатер с часами, а подле ворот по обе стороны карауль-ныя малыя палаты, да казенный амбар, а позадь ворот к новой Мещанской слободе часовня с кельями к Николаевскому монастырю, что на Перерве, а начато то строение строить в лето 7200 (1692), а совершено 7203 (1695), а в то время будущего у того полку стольника и полковника Лаврентия Панкратьева сына Сухарева».
В 1698 году Петр, возвратясь из-за границы, надстроил над вторым этажом башни третий, с шатровыми же крышами, столб башни увеличил еще на два яруса и пристроил к башне с восточной стороны открытое крыльцо «в два рундука (марша)», не шедшее, однако, прямо, как ныне, а на средине поворачивавшее с площадки под прямым углом к Земляному городу, то есть выходившее нижней своей частью на внутренний проезд Садовой, к Сретенке. Постройка была окончена в 1701 году, и в Сухаревой башне, взамен уничтоженных стрелецких полков, была размещена «Математическая и навигационная школа» — первое в России высшее специальное учебное заведение, готовившее штурманов, геодезистов и проч. Имя строителя башни доселе точно не установлено. По одним предположениям, она строилась по планам и под непосредственным «смотрением» самого Петра, по другим, более вероятным, — под руководством Михаила Ивановича Чеглокова, строителя многих казенных сооружений Петра I
Стиль Сухаревой башни — смесь ломбардского с готическим [13].
Построена башня из красного кирпича, приблизительно в полтора раза большего по размеру, чем нынешний кирпич. Окна, двери, пилястры и другие части отделаны белым камнем. Вероятно, вначале башня не была окрашена и представляла собою естественное сочетание цветных материалов, из которых она была построена. Позднее башня окрашивалась в красный, желтый, зеленый и «дикий» [14] цвета.