Малик родился в богатой семье этнических узбеков в провинции Фарьяб. После смерти отца главой семьи стал его брат Расул Палаван.
В восьмидесятые годы Малик вслед за Палаваном вступил в ряды подчинявшейся генералу Дустуму так называемой "узбекской милиции" — неофициального вооруженного формирования, сотрудничавшего с коммунистическим правительством.
С 1992 года Малик занял пост министра иностранных дел в теневом правительстве генерала Дустума, созданным незадолго до краха коммунистической власти в Афганистане. В 1992 году войска Дустума, в том числе и "узбекская милиция", перешли на сторону моджахедов, что привело к взятию Кабула антикоммунистическими силами.
Пришедший к власти президент Бурхануддин Раббани был союзником Дустума, но из-за того, что Палаван находился в плохих отношениях с военными руководителями моджахедов, ни он, ни Малик не смогли занять серьезных постов.
Зато Палаван обладал серьезной властью в своей родной провинции Фарьяб и, по слухам, готовился свергнуть Дустума и стать лидером северной части Афганистана. В июне прошлого года Палаван был убит. Малик, вернувшийся с конференции ООН в Нью-Йорке, взял под свое командование армию брата и занял пост губернатора провинции. Несмотря на слухи о причастности Дустума к убийству брата, Малик до последних дней сохранял внешне хорошие отношения с Дустумом.