Kolontarova was born with the name Mazol to Yashuva Kolontarov and Tamara Khanimova Kolontarova (both originally from Samarkand, Uzbekistan), a religious Bukharian Jewish family in Dushanbe, Tajikistan and was the youngest of her 5 sisters and 2 brothers. Mazol's father Yashuva wanted her to become a hairdresser like her older sisters but Malika refused and wanted to become a dancer instead. Her father later on let her pursue a career in dancing. Even though Kolontarova was rebellious as a child and had bigger dreams, she never forgot her roots even when she became famous. Being Jewish was looked down upon in the Soviet Union and in Tajikistan but Malika proudly identified herself as a Bukharian Jew stating that since she is famous and admired, she does not feel the need to hide her Jewish identity. "Most Jewish people [in Tajikistan] say they are Tajik or they are Russian because Jews get no good work, no good pay," she says, "But once I’m famous, I’m not afraid. I say, 'Me Jewish.'"  Kolontarova was trained in dance by Gh. Valamatzoda and Remziye Bakkal. Her director wanted her to change her name from Mazol to Malika. He said that Mazol sounded "too Jewish" and Malika means Queen in Arabic and Kolontarova danced like a Queen.
Malika began her career in 1965 with "Lola Dance Ensemble" and later on went to the "Worker Resources." From the beginning, her dance moves were completely in sync with the music. Kolantarova became one of the most famous entertainers in the USSR and in Central Asia. She performed all over the Soviet Union and all over Asia, not just in Central Asia. She was well known for her folk dances and the dances she created became a part of the Central Asian artistic culture. Kolontarova toured and performed different cultural dances in nations such as Japan, Afghanistan, Spain, Turkey, Russia and India. While in India, she appeared in some Bollywood films in the 1970s.
Kolontarova married Ilyas Gulkarov, a Bukharian Jewish doira player and "Honored Artist of Tajikistan."  The two went on tour in Europe, Asia, and all over the Soviet Union. Kolontarova was given the country's highest honor when she was named People's Artist of USSR in 1984, becoming the only woman from Tajikistan to receive the title, after receiving the awards of "People's Artist of Tajikistan" in 1976 and "Honored Artist of Tajikistan" in 1972.
Kolontarova conquered the world with her fiery dancing. According to Igor Mosev, a director of an ethnic dance ensemble in the USSR, Malika is "an Eastern miracle" and she "made a revolution in Eastern popular dancing."
In 1993, Malika and her family moved to Queens, New York, United States during the collapse of the USSR to escape the poverty in Tajikistan. In America, Kolontarova continued her dancing career by opening up the "Malika's International Dance School" to teach young girls how to dance.