Mosolov was born to an upper-middle-class family in Kiev, in the Russian Empire. His mother, Nina Alexandrovna, was a professional singer at the Bolshoi Theater and a graduate of the Kiev school of music, and she gave Mosolov his first musical lessons. The family moved to Moscow in 1904. Mosolov's father, Vasiliy Alexandrovich, died a year later when Mosolov was five years old. After his father's death, Mosolov's mother married a successful painter and teacher, Mikhail Leblan. Young Mosolov was greatly impacted by the cosmopolitan lifestyle into which he was raised; both German and French were spoken in the home and the family took trips to Berlin, Paris, and London.