Rustamov was born on 19 August 1970 in Xıdırlı village of Agdam raion of Azerbaijan SSR. After graduating from the secondary school in Xıdırlı village, he continued his education at Agdam Vocational School No. 50. From 1988 through 1990, Rustamov served in the Soviet Armed Forces. In 1991 he entered the Police Regiment of Agdam District Department of Internal Affairs.
