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 possibilty to determine the sex of the specimen. In this study, we have analysed eleven 5000 year-old human teeth from a French Neolithic site to set up dedicated paleoproteomics strategies for phenotypic and taxonomic characterization of ancient samples. We have developed an optimized 3-step iterative search strategy using a custom human protein database of shotgun proteomics nanoLC-MS/MS data. This allowed the identification of a total number of 1496 proteins in two replicate experiments. Most of the proteins were identified thanks to the no-enzyme database search mode included in the dedicated bioinformatics data analysis pipeline based on iterative database search strategy. In particular, in addition to specific tooth proteins, this optimized shotgun proteomics approach led to the identification of two other proteins of interest, cementum protein 1 (CEMP1) and collagen alpha-1(X) (COL10A1). Noteworthy, the presence of single amino acid variations K55E and D128N could also be identified in CEMP1 and COL10A1, respectively. These polymorphisms are rarely found in the European population today. We have also designed a targeted nanoLC-PRM strategy using the sex specific peptides TALVLTPLK and IALVLTPLK of the AMELX and AMELY proteins. This sensitive approach allowed to successfully identify the sex of the individuals in 91% of the samples.