From the Huffington Post:
We probably don’t know exactly when a substance was first used on teeth. But research suggests that the Ancient Egyptians first developed a dental cream as far back as 3000-5000 BC. This dental cream was comprised of powdered ashes from oxen hooves, myrrh, egg shells, pumice, and water the actual “toothpaste” was likely a powder at first, with the water probably added at the time of use. And while it probably tasted terrible, it likely provided a somewhat minimum level of tooth cleaning, at least in a “scraping away the bad stuff” sense.
Later, in Greece and Rome, we see more abrasives being added to the powder mixture, like crushed bones and oyster shells. More cleaning power, for sure, but still, the taste… Well, maybe it’s not so bad. We know the Romans added flavoring, perhaps to help with bad breath and to make their paste more palatable. This flavoring was more or less powdered charcoal and bark I’m not sure how tasty powdered charcoal really is, though.
via Thomas P. Connelly, D.D.S.: The History of Toothpaste: From 5000 BC to the Present.
Source??? At least they don’t take Spaniards in Catullus as indicative of Roman practice …
rogueclassicism 
Having read Apuleius’ Apologia in college, I will never forget that the opening arguments contain, among other things, a poem about toothpaste (1.6):
Calpurniane, salue properis uersibus.
misi, ut petisti, [tibi] munditias dentium,
nitelas oris ex Arabicis frugibus,
tenuem, candificum, nobilem puluisculum,
complanatorem tumidulae gingiuulae,
conuerritorem pridianae reliquiae,
ne qua uisatur tetra labes sordium,
restrictis forte si labellis riseris.
Granted, there’s no crushed bones and oyster shells (just some unidentified Arabicae fruges), but it’s a pretty delightful poem.
dentifricium (“toothpaste”) is often thought to be a mediaeval Latin term, but it’s already found and described in Scribonius and Pliny, which are most probably the sources for Connelly:
Plin. NH 28.49, 29.11
(the word used in the English translation is “dentrifice”)
Scrib. Comp. 59.1–60.13: