Tooth is a remarkable source of information for paleoanthropologists. Investigation of ancient dental proteomes is able to provide biomolecular data helping at understanding past life. In particular, the enamel protein amelogenin (AMEL) offers the possibility to determine the sex of the specimen. Here, we have analysed eleven 5000 year-old human teeth from a French Neolithic site using a dedicated paleoproteomics strategy for phenotypic characterization of ancient samples. We have set up a shotgun proteomics analysis based on an optimized 3-step iterative search strategy. This allowed the identification of a total number of 1496 proteins including the main proteins characteristic of dental tissues. Most of the proteins were identified by the no enzyme database search mode included in the iterative bioinformatics data analysis pipeline. This demonstrates that a number of peptides issued from randomly degraded proteins may be missed when using the conventional semi-tryptic database search mode. Based on the identification of the sex-specific peptides TALVLTPLK, IALVLTPLK and WYQSIRPPYP of amelogenin, a targeted MS approach using a parallel reaction monitoring (PRM) mode was performed to maximize the sensitivity and the reproducibility of detecting these unique peptides for sex estimation. This led to confirm the sex of individualsin all the samples.