Objectives: During the microscopic examination of the Neandertal dentitions from El Sidron (Spain) and Hortus (France), we found unusual fine parallel microstriations on the mesial and distal sides of all tooth types, near the cervix. As its appearance was similar to toothpick grooves described in other Homo species, it could correspond to early stages on its formation. To test this hypothesis we developed an experimental replication of a groove using grass stalks. Materials and Methods: Comparisons between 204 isolated Neandertal teeth and the two experimental dental specimens corroborate that the marks correspond to initial stages of toothpick groove formation, and we propose a five-grade recording scale that summarized the groove formation process. Results: Using this new recording procedure, we found that Hortus individuals have higher incidence of this trait (eight individuals out of nine) than the El Sidron individuals (nine out of 11). Toothpick grooves from El Sidron show the earliest stages of development, whereas the grooves found on Hortus Neandertals were well-developed. Toothpick grooves were also found in 21 incisors and canines. Conclusions: These differences could be due to the more advanced occlusal dental wear in Hortus individuals, maybe age-related and with a more meat-based diet maybe favoring the inclusion of food debris and thus probing as the cleaning methodology. Our results allow the identification and characterization of incipient toothpick grooves on the human fossil record and contribute to increase our knowledge on Neandertals behavioral and oral care habits.