Rozhdestvensky was born in Leningrad and studied engineering at the Higher Military Engineering School of the Soviet Navy in Pushkin. From 1961 to 1965 he was commander of a deep sea diving unit in the Baltic Sea War Fleet. 