It's called a byname or epithet and it went out of style once fixed surnames and more complicated patronymic surnames were adopted. "The Great" was usually an honorific new epithet given to a well-liked political leader whose original epithet had been mundane: "John the Red" or "John at the Creek" or some such thing.

This previous answer I have given in this sub before goes into the detail of how fixed surnames came to replace that older system of bynames/epithets. There's no one answer as to when they were replaced since it happened location by location over hundreds of years. The earliest replacement of epithets with fixed surnames happened in England and France around the time of the Norman Invasion in 1066. Most other European locales went from epithets to some system of patronymics before going to fixed surnames.