Parajanov was born Sarkis Hovsepi Parajaniants (Սարգիս Հովսեփի Փարաջանյանց) to artistically gifted Armenian parents, Iosif Paradjanov and Siranush Bejanova, in Tbilisi, Georgia. (The family name of Parajaniants is attested by a surviving historical document at the Sergei Parajanov Museum in Yerevan.) He gained access to art from an early age. In 1945, he traveled to Moscow, enrolled in the directing department at the VGIK, one of the oldest and highly respected film schools in Europe, and studied under the tutelage of directors Igor Savchenko and Aleksandr Dovzhenko.
In 1948 he was convicted of homosexual acts (which were illegal at the time in the Soviet Union) with a MGB officer named Nikolai Mikava in Tbilisi. He was sentenced to five years in prison, but was released under an amnesty after three months. In video interviews, friends and relatives contest the truthfulness of anything he was charged with. They speculate the punishment may have been a form of political retaliation for his rebellious views.
In 1950 Parajanov married his first wife, Nigyar Kerimova, in Moscow. She came from a Muslim Tatar family and converted to Eastern Orthodox Christianity to marry Parajanov. She was later murdered by her relatives because of her conversion. After her murder Parajanov left Russia for Kiev, Ukraine, where he produced a few documentaries (Dumka, Golden Hands, Natalia Uzhvy) and a handful of narrative films: Andriesh (based on a fairy tale by the Moldovan writer Emilian Bukov), The Top Guy (a kolkhoz musical), Ukrainian Rhapsody (a wartime melodrama), and Flower on the Stone (about a religious cult infiltrating a mining town in the Donets Basin). He became fluent in Ukrainian and married his second wife, Svitlana Ivanivna Shcherbatiuk, also known as Svetlana Sherbatiuk or Svetlana Parajanov, in 1956. Shcherbatiuk gave birth to a son, Suren, in 1958.