Ранние работы А. А. Холодовича были в основном посвящены грамматике корейского и японского языков (в их числе монографические описания синтаксиса японского военного языка и строя корейского языка). В работах 1960–1970-х гг. он выступил как новатор и оригинальный теоретик, выдвинувший программу типологического изучения грамматических категорий в языках мира, предложивший получившую широкое признание теорию залога (в соавторстве с И. А. Мельчуком). По намеченной им программе исследований и под его руководством были осуществлены коллективные описания каузативных (1969) и пассивных (1974) конструкций. Под его редакцией и с его комментариями вышло русское издание всех основных работ Ф. де Соссюра (1977); им был переведен на русский язык классический труд Н. С. Трубецкого «Основы фонологии» (М.: URSS).