I can only comment on the phenomenon as it takes place in Italy; my guess is that the answer to this question will vary depending on where you're looking. Even within Italy there is variation, so you might get a better answer if you clarify your parameters.

In Italy, the practice of attaching a second name to a person’s first name for the purpose of identification became increasingly common in the 10th and 12th centuries, although only after the 12th century did the practice of passing a name from generation to generation develop. The two-name system was by that point rather standardized and generalized in some areas, such as Genoa—BUT the degree of standardization and frequency varied across the peninsula, and through the 14th and 15th centuries hereditary family names were typically reserved for upper-class citizens. For example: the 1427 catasto (loosely speaking, a tax assessment) in Tuscany provides illustrative data: Florence had the highest incidence of families with a last name, at 36.7%; this figure drops to a fifth in secondary cities, and then to a tenth in the countryside.

In general, when secondary names begin to appear in Italy during the Middle Ages they appear in the following forms:

• patronymic, referring to the individual’s paternal ancestry via either the genitive (Goro Gregorii, i.e., "Goro [son of] Gregorio") or with a preposition and the ablative (Nicola de Bartolomeo, i.e., "Nicola [son] of Bartolomeo");

• toponymic, using either de and the ablative place-name (Augustinus de Florentia, i.e., "Augustinus of Florence") or a “topographic” adjective (Johannes Pisanus, i.e,. "Johannes [the] Pisan");

• and epithetic, using either an adjective (Johannes Albus) or a noun (Gualterius Buccarellus).

To sum up: by about the 12th century, in some parts of Italy, last names were becoming commonplace for the upper classes.

Again, I'd stress that there is great variability based on location and socioeconomic status, among other factors, so there is no one answer that will cover the broad question. But I hope this helps clarify one corner of the world!

Some sources worth checking out are below; the first two provided much of the information here:

Gianluca D’Acunti, “I nomi di persona”, in Storia della lingua italiana, ed. Luca Serianni and Pietro Trifone, 3 vols., vol. II, Scritto e parlato (Turin: Giulio Einaudi editore, 1994): 795-857

Alberto Zamboni, “I nomi di luogo”, in Storia della lingua italiana, ed. Luca Serianni and Pietro Trifone, 3 vols., vol. II, Scritto e parlato (Turin: Giulio Einaudi editore, 1994): 859-78

Carlo Alberto Mastrelli, “La recherché onomastique en Italie”, in Namenforschung. Ein internationales Handbuch zur Onomastik, eds. Ernst Eichler, Gerold Hilty, Heinrich Löffler, Hugo Steger, and Ladislav Zgusta, 3 vols. (Berlin: Walter de Gruyter, 1995): 163-71; and Wolfgang Haubrichs, “Namendeutung im europäischen Mittelalter” in ibid., pp. 351-60

Richard W. Emery, “The Use of the Surname in the Study of Medieval Economic History” (Medievalia et Humanistica VII, 1952): 43-50

Robert Sabatino Lopez, “Concerning Surnames and Places of Origin” (Medievalia et Humanistica VIII, 1954): 6-16

Richard W. Emery, "A Further Note on Medieval Surnames” (Medievalia et Humanistica IX, 1955): 104-6

This was a fantastic answer. Thank you!! I figured there wouldn’t be a standard answer applying to the entire world, but this is a great insight into Italian history and culture.

As /u/aldusmanutius suggested, it varies based on culture, from "from the earliest written records" to "still hasn't happened yet". Did you have a specific culture in mind?

There's a further question: what do you mean by "last name"? An inherited distinguisher? A standard distinguisher that is not inherited (Madoc ap Eynon, but his father was Eynon ap Gronou)? A descriptive distinguisher?

(As a pedantic note, even inherited names are not necessarily "last"; see Chinese, Japanese, or Hungarian. Terminology differs from different people, but I think "surname" is best for the general concept.)