TL;DR: the tria nomina were dead before the empire was, so pre-Romance times.
Long version: The tria nomina system is the most famous used in ancient Rome, but it wasn't by any means universal. It had already started to fade out in the first century.
Around this time, the upper classes started using multiple nomina to indicate extra familial relationships, both through the female line and through adoption. This quickly got to ridiculous levels: one second-century consul was named Quintus Pompeius Senecio Roscius Murena Coelius Sextus Iulius Frontinus Silius Decianus Gaius Iulius Eurycles Herculaneus Lucius Vibullius Pius Augustanus Alpinus Bellicius Sollers Iulius Aper Ducenius Proculus Rutilianus Rufinus Silius Valens Valerius Niger Claudius Fuscus Saxa Amyntianus Sosius Priscus.
Now that nomina were getting used so much, praenomina started fossilizing: they just weren't that relevant. Everyone in the same family would get the same praenomen for official purposes but it would never really be used in day-to-day life.
Then in the third century, the emperor Caracalla gave citizenship to all freedmen in the entire empire. And all those freedmen, by custom, gained the praenomen "Marcus" and nomen "Aurelius". So now neither of those was very useful unless you were from an old family.
At this point people just used cognomina if they had them, or took on nicknames (signa), since the official names were basically useless for their original purpose. And this trend continued steadily until the end of the empire, when people gave up on the official names entirely and just used their signa for everything.