Bacterial cell wall components have been previously used as infection biomarkers detectable by antibodies. However, it is possible that the surface of the Mycobacterium tuberculosis (M. tb), the causative agent of tuberculosis (TB), also possesses molecules which might be non-antigenic. This makes the probing of biomarkers on the surface of M. tb cell wall difficult using antibodies. Here we demonstrate the use of phage display technology to identify peptides that bind to mycobacteria. We identified these clones using both random clone picking and high throughput sequencing. We demonstrate that random clone picking does not necessarily identify highly enriched clones. We further showed that the clone displaying the CPLHARLPC peptide which was identified by Illumina sequencing as the most enriched, binds better to mycobacteria than three clones selected by random picking. Using surface plasmon resonance, we showed that chemically synthesised CPLHARLPC peptide binds to a 15 KDa peptide from M.tb H37Rv whole cell lysates. These observations demonstrate that phage display technology combined with high-throughput sequencing is a powerful tool to identify peptides that can be used for investigating potential non-antigenic biomarkers for TB and other bacterial infections.