Работал ассистентом режиссёра на съёмках кинофильма «Освобождение» (1972), был вторым режиссёром на картине «Соло для слона с оркестром» (1975). Его дебютная полнометражная лента «В зоне особого внимания» (1978) была отмечена Серебряной медалью имени А. Довженко и Государственной премией РСФСР имени братьев Васильевых. В 1979 году по своему сценарию он поставил драму «Безответная любовь», через два года вышел фильм «34-й скорый». Среди других фильмов Андрея Малюкова – «Верными останемся» (1988), «Делай – раз!» (1990), «Любовь на острове смерти» (1991), «Бабочки» (1991), «Маленькие человечки Большевистского переулка, или Хочу пива» (1993). В 1996 году картина «Я – русский солдат» (1995) была удостоена Большого специального приза на кинофестивале «Золотой витязь» (Минск). С конца 1990-х годов режиссёр активно работает на телевидении, поставил в 2000 году сериал «Империя под ударом», а в 2002 году на телеэкраны вышел приключенческий сериал «Спецназ».