Анатолий Иванович Мальцев родился 27 (14) ноября 1909 года в Мишеронском, в семье стеклодува Мишеронского стекольного завода Мальцева Ивана Александровича. Окончил школу в 1927 году, после чего поступил в Московский университет. Учась на четвёртом курсе, начал работать ассистентом кафедры высшей математики Московского института технологии зерна и муки.
По окончании МГУ в 1931 году Мальцев был направлен на работу в Иваново, где работал сначала ассистентом кафедры высшей математики Энергетического института, а затем перешёл на работу в Ивановский государственный педагогический институт (ныне ИвГУ), где работал до 1960 года.
С 1934 по 1937 год Мальцев учится в аспирантуре МГУ под руководством А. Н. Колмогорова. В 1937 году Мальцев защищает кандидатскую диссертацию «Абелевы группы конечного ранга без кручения».
В 1936 году Мальцев доказал одну из основных теорем математической логики, известную сейчас как локальная теорема Мальцева. Созданный им метод «описания моделей» позволил дать общее решение ряда проблем, ранее решавшихся с частных позиций.
C 1939 по 1941 год Мальцев учится в докторантуре Математического института им. В. А. Стеклова. В 1941 году после защиты докторской диссертации «Структура изоморфно представимых бесконечных алгебр и групп» он становится старшим научным сотрудником этого института.
В 1946 году Анатолий Иванович получает Сталинскую премию 2-й степени за работы в области теории групп.
В 1953 году Мальцева избирают членом-корреспондентом Академии Наук СССР.
В 1956 году за выдающиеся заслуги в области науки Мальцеву присвоено звание Заслуженного деятеля науки РСФСР.
В 1958 году академик М. А. Лаврентьев приглашает Мальцева на работу в Сибирский научный центр. В том же году Мальцева избирают действительным членом Академии наук СССР.
В 1959 году Мальцев переезжает в Новосибирский Академгородок. С 1960 по 1967 год Мальцев заведует отделом алгебры Института математики СО АН СССР, а также заведует кафедрой алгебры и математической логики НГУ.
В 1964 году Мальцеву присвоено звание лауреата Ленинской премии за цикл работ по приложению математической логики к алгебре и теории моделей. В 1967 году Мальцева награждают орденом Ленина.
7 июня 1967 года Анатолий Иванович Мальцев скончался.
В 1947, 1950 и 1953 годах Мальцев был депутатом Ивановского областного Совета, а с 1951 по 1955 год — депутатом Верховного Совета СССР.
В 1931 году Мальцев женился на своей сокурснице Наталье Петровне Гостик, дочь Людмила (род. 1932), сыновья Аркадий (род. 1935), Иван (род. 1945), Андрей (род. 1951).