Появился на свет будущий математик в тихом провинциальном городке Гжатске (ныне Гагарин). В 1922 году, сдав экстерном экзамены по программе общеобразовательной школы, шестнадцатилетний Андрей поступил на физико-математический факультет Московского университета. На втором курсе он начал заниматься научной работой, посещал топологический семинар профессора Павла Сергеевича Александрова. В 1925‒1926 годах в немецком научном журнале Mathematische Annalen были опубликованы три его статьи. В них излагались результаты, которые профессор Александров оценил как серьезные открытия. Теперь они считаются классическими.
В 1927 году Андрей Тихонов окончил математическое отделение физмата МГУ, а в 1930-м — аспирантуру Научно-исследовательского института математики при МГУ, и его оставили в университете преподавателем. В 1933 году, после прошедшей в МГУ реорганизации, в ходе которой физико-математический факультет был разделен на механико-математический и физический, Тихонов был направлен на вновь организованную кафедру математики физического факультета.