Окончил Ленинградский университет (1927); преподавал на Восточном факультете ЛГУ, в разные годы заведовал кафедрами корейской, китайской, японской филологии. С 1961 года — в ЛО Института языкознания АН СССР, где руководил созданной им группой структурно-типологического изучения языков.
Ранние работы в основном по грамматике корейского и японского языков, в том числе монографические описания синтаксиса японского военного языка (1937) и строя корейского языка. В терминологии этих работ и в подходе к фактам языка частично прослеживается влияние идей Н. Я. Марра; специалисты в настоящее время оценивают эти работы как в целом устаревшие, несмотря на отдельные проницательные суждения и удачные описательные решения.
В работах 1960—1970 гг., напротив, Холодович выступает как смелый новатор и оригинальный теоретик, выдвинувший программу типологического изучения грамматических категорий в языках мира (универсальной грамматической «библиотеки смыслов»). С начала 1960-х гг. он стал одним из первых (в отечественной теории грамматики) сторонников вербоцентрического подхода к синтаксису предложения (возможно, под влиянием работ Л. Теньера). В соавторстве с И. А. Мельчуком предложил теорию залога, основанную на исчислении всех возможных значений грамматической категории. По намеченной Холодовичем программе исследований и под его руководством были осуществлены коллективные описания каузативных (1969) и пассивных (1974) конструкций; эта работа была продолжена и после его смерти в рамках деятельности петербургской типологической школы.
Как и В. А. Звегинцев, Холодович обладал острым чувством нового и стремился поддерживать молодых исследователей, а также пропагандировать мало известные в СССР в то время достижения лингвистики XX века. Им была переведена на русский язык книга Н. С. Трубецкого «Основы фонологии» (1960); под его редакцией и с его комментариями вышло русское издание всех основных работ Ф. де Соссюра (1977), включающее в том числе и новый перевод «Курса общей лингвистики» (в настоящее время общепринятый).
Основные работы А. А. Холодовича собраны в посмертном сборнике «Проблемы грамматической теории» (Л., 1979); там же имеется библиография его трудов.
Публикации по корейскому языку: