Участник похода генерала М. Г. Черняева в мае - июне 1865 года на Ташкент. Во время штурма Ташкента священник А. Е. Малов был в числе первых воинов, взобравшихся на стены укрепления города у Камаланских ворот города, за что получил «Георгиевский» наперсный крест. Вот что писал об этом Д. Н. Логофет:
В 1870 году отказался от епископского сана. Его зять — муж единственной дочери Елизаветы (1841—1927) — штабс-капитан Лев Ефимович Коржев погиб при первом штурме Ташкента в октябре 1864 году и был похоронен в числе других русских воинов в братской могиле в Ташкенте. Павшие при штурме Ташкента в июне 1965 года воины были похоронены у Камаланских ворот городской стены Ташкента. Позднее здесь была воздвигнута часовня в память павших воинов: «… по ходатайству лиц, участвующих во взятии Ташкента, … Генерал-Губернатор разрешил сооружение памятника над могилою павших воинов на геройском штурме этого города, для чего предоставил им избрать из своей среды распорядительный комитетъ и открыть подписку в пределах Туркестанского края. В силу этого разрешения, участниками взятия Ташкента избран распорядительный комитет из председателя — протоиерея Малова…».
При непосредственном участии А. Е. Малова осуществлялась постройка Военного собора с Ташкенте, первым настоятелем которого и стал священник Малов.
После смерти Андрея Ефграфовича Малова, последовавшей 3 апреля 1899 года, он был похоронен у северной стены левого придела Ташкентского военного Спасо-Преображенского собора.
