I think I’ve seen the claim that most Japanese had no surnames until the Meiji period somewhere on Wikipedia (and maybe you, too?).
However! Nothing could be further from the truth.
* * * * * * * * *
For as long as history (i.e., written records contemporary of their time), Japanese people did have surnames of some sorts, centuries before (medieval) Europe had the glorious idea to start using surnames. (To be fair, the Japanese also most likely just borrowed the idea from the Chinese.)
The ritsuryō state mandated surnames for every freeman (i.e., commoners, but not slaves. Slaves had no surnames.), around the Taika Reforms of 645 at the latest. More accurately, this was a clan name (ujina, later: sei), shared by entire lineage groups having a common ancestor—possibly hundreds of people thus shared a common surname.
In the medieval period, from the 11th century onward, a concept akin of the modern surname—a family name (myōji)—emerged: on the one hand, noblemen in the capital came to be referred to by the name of their residence instead of their clan name, on the other, warriors started taking the name of the place their governed as a byname. This can be observed as early as the eleventh century. By the late 13th, early 14th century, these names became firmly attached to specific lineages, thus having become family names. By the late 15th century, most commoners had adapted the practice as well. This means that people now had two different types of surnames.
But around the 12th century, we also observe that commoners stopped using their surnames (of both kinds) in official documents dealing with people of higher status. We don’t know when or why exactly due to a lack of sources, but the most believable theory is that using a surname in public came to imply being of the ruling classes, so those who weren’t eventually stopped using them in official interactions; however, documents signed in private, such as secret agreements that the officials were not supposed to see, do note surnames; documents stored at Shinto shrines which record the names given to commoner children do mention surnames, and so on.[1]
In the Edo period, the public usage of surnames by commoners became forbidden by law. This was just one means of segregating the now-ruling samurai class from the common people. Still, there were some exceptions: either specific professions such as doctors, Confucian scholars, sumo wrestlers, or simply people who donated a lot of money for the greater good (such as public maintenance and construction projects, or canceling the massive debt of a high-ranked samurai…).
The Meiji government changed things: since having a single name and a surname was the modern thing to do, they decreed on September 19th 1870 that from now on, all common people were permitted to use surnames in public, as a consequence of the abolishment of the Edo period's status divisions.[2] On Feburary 23rd 1975, another law proclaimed that this initial permission now became mandatory—in cases were the surname was not known, taking on a new surname was permitted (surnames were required to be recorded in the national census registers the modern state had commenced to compile).[3] For some unfathomable reason, this law is often misrepresented as “from now on, everyone has to have a surname, and before this, many people didn't have one.” (To this I can only say, people, learn how to read. Its very clear that this is stated nowhere whatsoever.)
* * * * * * * * *