9 мая 2005 года в Тобольске, на здании Филиала государственного архива Тюменской области, располагающегося в одном из корпусов Тюремного замка (1838, арх. В. В. Вайгель), установлен бюст (погрудный срез) Алексея Семёновича Шеина, выполненный в технике горельефа. Решение увековечить память о государственном и военном деятели петровской эпохи принадлежит региональному общественному фонду «Возрождение Тобольска». Именно на территории современного хранилища исторических документов, согласно карте Семёна Ремезова, находилась воеводская изба, где в 1680–1681 годах «сидел воеводой» будущий «покоритель Азова».

А. С. Шеин родился, предположительно, около 28 сентября 1652 года в семье спальника царя Алексея Михайловича Cемёна Ивановича Шеина. А. С. Шеин начинал службу стольником царевича Алексея Алексеевича, а после его кончины в 1670 году пожалован спальником царя Алексея Михайловича.

Не позднее ноября 1679 года А. С. Шеина был назначили на воеводство в Тобольск. Он приехал в город 6 апреля 1680 года и пробыл там год и девять месяцев. За время его воеводства в Тобольске случился пожар: 7 августа 1680 года город почти полностью выгорел. Под присмотром А. С. Шеина Тобольск был заново отстроен: поставлена новая приказная палата, острог и две церкви.

По возвращении из Тобольска А. С. Шеин был пожалован боярством, участвовал в коронации царей Ивана и Петра Алексеевичей. В 1683–1684 годах – воевода Белгородского разряда с центром в Курске. В 1684 году был послан к южным границам для осмотра пограничных крепостей. В 1693 году среди прочих сопровождал Петра I в Архангельск. В 1687–1689 годах возглавлял Новгородский разрядный полк, прославился участием в Крымских походах 1687 и 1689 годов и в Азовском походе 1696 года. Перед этим походом, завершившимся взятием Азова, царь назначил А. С. Шеина главнокомандующим российским войском в должности воеводы Большого полка, которую он занимал до конца жизни. Утвердившаяся в историографии точка зрения, согласно которой в 1696 году А. С. Шеин получил чин генералиссимуса, не подтверждается официальными документами. В российской военной иерархии того времени такого чина не существовало. Первым отечественным генералиссимусом в 1727 году стал князь А. Д. Меншиков.

В феврале 1697 году назначен судьей Иноземского, Рейтарского и Пушкарского приказов. В 1698 году он участвовал в подавлении стрелецкого бунта у стен подмосковного Новоиерусалимского монастыря, но впал в немилость предположительно из-за того, что не раскрыл связь бунтовщиков с царевной Софьей Алексеевной.

А. С. Шеин скончался 2 февраля 1700 года в Москве и был погребён в фамильном склепе у церкви Сошествия Святого Духа Троице-Сергиева монастыря. На похоронах присутствовал Пётр I, надгробную речь произнёс Стефан Яворский. Могила военачальника уничтожена в 1920-х годах, не сохранилась и Знаменская церковь (затоплена водами Учинского водохранилища), построенная на средства С. А. Шеина в его подмосковной усадьбе Курово (Пушкинский район) – вотчине Шеиных.

Род Шейных пресёкся на детях Алексея Семёновича. Полководец был четырежды женат: первый раз – на Анне Петровне, дочери окольничего князя Петра Алексеевича Долгорукова. А после ее кончины (†1667) женился на дочери князя Ивана Ивановича Лобанова-Ростовского Степаниде (†1674). Третья жена Анна Петровна скончалась в 1677 году. Четвертой женой стала дочь стольника Михаила Васильевича Приклонского и Федосьи Дмитриевны Горихвостовой Марфа. В 1680–1682 годах Приклонский по родству стал товарищем (помощником) А. С. Шеина во время воеводства в Тобольске. Есть сведения о двух сыновьях полководца – Петре и Сергее, который в 1708 году был отправлен Петром I в Европу для обучения навигаторскому искусству.

Автор памятника С. А. Шеину скульптор М. О. Лушников. Бронзовый бюст установлен на консоли, крепящейся к стене. В основании консоли размещён следующий текст: «Алексей Семенович Шеин / 1662–1700 / Первый российский / генералиссимус / в 1680–1682 гг. тобольский / разрядный воевода / На этом месте / в последней четверти / XVII в начале XVIII вв. / находился / воеводский двор».

Шеин предстаёт облачённым в боярскую одежду – украшенный меховым воротником кафтан (ферязь) с тремя нашивками и шапку с пером и меховой оторочкой. Скульптор изобразил Шеина периода его тобольского воеводства – в усах и бороде. Обязательное бритьё бороды было введено Петром I в 1698 году. Согласно распространённой легенде, когда Пётр I начал собственноручно стричь бороды, первым, кто подвергся этой процедуре, был А. С. Шеин, впавший в немилость после стрелецкого восстания 1698 года. C 1699 года с мужчин, носящих бороду, взималась особая пошлина, уплатившим её, выдавалась специально отчеканенный жетон – бородовой знак.