In his early childhood, Starostin sang in a boys choir led by Vadim Sudakov. He started to play clarinet in school, and later graduated from Merzlyakov college of music, and then from the Moscow Conservatory.[3] After graduation, he switched to playing folk instruments. By mid-90s, he collaborated with jazz musicians Mikhail Alperin and Arkady Shilkloper, forming a Moscow Art Trio group, and mixing together jazz and traditional music. In his songs, Starostin avoids harmonising, staying within certain scales rather than sticking to chord patterns, which makes jazz played this way more "compatible" with traditional folk music.[4] As of 2011, Starostin moved from jazz and rock compositions back to traditional folk performances.[5]
He participated in folk music research expeditions, and recorded thousands of songs.[6] In 1991, Starostin produced a series of TV programs called World Village,[7] and as of 2008, runs a different program named Wanderings of a musician on Russia-K.[8] In 2006, he worked as a producer for the animated feature film Prince Vladimir.[9]
While many CDs and concert programs feature Starostin playing "Rozhok", it worth mentioning that actually he plays not the folk wooden trumpet, known as a Rozhok, but a "Tverskoy Rozhok", which is a reed instrument,[10] is also known as zhaleyka.[11]
