Prior to the invention of toothpaste, humans around the world used crushed eggshells, oyster shells, ashes, charcoal, chalk and even salt as abrasives to scrub their teeth with. As for implements, the historical record shows that the Chinese were using a primitive brush with hog bristles attached to a bone or bamboo handle during the Tang Dynasty (619-907). But the oldest toothbrushing implement we have evidence of is the chew stick, which first pops up in Mesopotamia around 3500 B.C.
Called a miswak in Arabic, the chew stick was a twig taken from the Salvadora Persica tree. "Different cultures have used twigs from trees and shrubs with wood grain that is very intertwined," Scott Swank, a dentist, historian, and curator of the National Museum of Dentistry, told Collectors Weekly. "You peel the bark off and chew it to get the fibers to fray out, and then you use those frayed fibers to clean your teeth."
Incredibly, the miswak is still in use today in some parts of Africa, the Middle East and Southeast Asia. Over the centuries, it's outlived some briefly-experimented-with toothbrush form factors like these:
Toothbrushes at the National Museum of Dentistry include, from left to right: A miswak or chew stick, an early 20th century celluloid toothbrush by Taub, a rubber-tipped gum stimulator and toothbrush from pre-1945, a Strockway rotary toothbrush from the 1950s, a Dr. Mayland's rubber toothbrush from the 1920s, a 1930s Rotor toothbrush, and another chew stick.