Улица Урицкого (бывшая Андреевская) начинается от улицы Дзержинского (бывшая Большая Солдатская), пересекает улицы Сакко и Ванцетти (бывшая Волоховская), Гагарина (Ротная) и заканчивается улицей Пролетарская стрелка (бывшая Пятницкая стрелка). Улица называлась так по церкви апостола Андрея Первозванного.
Деревянная Апостоло-Андреевская церковь была построена в 1646 г. Документы называют строителем церкви каменных дел подмастерье Корнилия Переволоку. В 1749 г. был освящен придел во имя Авраамия Затворника, а в 1755 г. во имя Андрея Первозванного. В 1885 г. была открыта Апостоло-Андреевская церковно-приходская школа.
В штате церкви значились священник и псаломщик. В церкви в разные годы служили священники Симеон Васильев, Симеон Лаврентьев, Иоанн Данилов, Иоанн Сентяшев, Вячеслав Глубоковский, Андрей Катаев.
Поскольку приход Андреевской церкви в старинном Тобольске был самым дальним и самым бедным, на улице преобладали одноэтажные деревянные дома. Двухэтажные дома принадлежали тобольским мещанкам Татьяне Ивановне Чуклиной (ул. Андреевская, 3) и Масе Миновне Круткиной (ул. Андреевская, 5).
В первые годы советской власти улица получила новое имя — имя революционера Урицкого. Моисей Соломонович Урицкий (псевдоним Борецкий) — российский и советский революционный и политический деятель, прежде всего получивший известность после своего назначения на должность председателя Петроградской ЧК. Убит 30 августа 1918 г. Леонидом Каннегисером.
В своей исторической планировке улица сохранилась до нашего времени, хотя и не уцелели старинные деревянное дома, например, не осталось даже фотографий дома по улице Урицкого, 27.