If you notice one major thing about Ancient-(or Pre-Modern) History, the most well known and studied figures only have one name-(i.e. Homer, Aristotle, Virgil, Ovid, etc.). When was the last name introduced into World History? If I was to submit an educated guess, it probably began around the early years of the Roman Empire with the various Caesars, as well as with the Roman imperial census. (Again, this is just an educated guess).
First: Since the OP made the question based on roman and greek names, I'll ignore other countries in this answer.
Second: Let us make a difference between Greece and Rome. Usually in Greece people used only one name, while in Rome they used three (name, gens name and family name). Hence a Greek name would be like Nike, Plato, Aristotle, etc. Once in a while a person with a common name would be differenced by including its origin, best known example is Thales of Miletus. But Rome used longer name (for males usually), like Publius Cornelius Scipio, Quintus Fabius Maximus or Gaius Julius Caesar.
Third: Usually people uses the shortest name available, only including a family name, origin or other reference to make a distinction between people who share the same name. That's why some famous people might own a name shared by many; like Caesar or Alexander the great.
Even nowadays a person might own a name; like Warhol, Lennon or Shaquille, even if that name is common.
Summary: Last name has not been introducing in world history. Is basically a cultural use or a need whenever a name is shared by many.