Neither his place nor his date of birth are known. It is assumed that he was born circa 1510, most likely, in Moscow: he called himself a Muscovite even after his move to Lithuania, and in his afterword to the Lviv Apostle he named Moscow "our home, our fatherland and our kin". In 1935 a Russian historian of heraldry, Lukomsky, advanced the hypothesis that his printer's mark resembled the Szreniawa coat of arms of the Rahoza szlachta family, and that Fyodorov had a connection with that family either by descent or by adoption. No subsequent researchers have accepted that theory other than Nemirovsky (2002), who agreed only with the possibility of adoption but not with the theory of Fyodorov's descent from the szlachta.