Sortases are enzymes that anchor surface proteins to the cell wall of Gram-positive bacteria by cleaving a sorting motif located in the C-terminus of the protein substrate. The best-characterized motif is LPXTG, which is cleaved between the T and G residues. In this study, a non-gel proteomic approach was used to identify surface proteins recognized by the two sortases of Listeria monocytogenes, SrtA and SrtB. Material containing peptidoglycan and strongly associated proteins was purified from sortase-defective mutants, digested with trypsin, and the resulting peptide mixture analysed by two-dimensional nano-liquid chromatography coupled to ion-trap mass spectrometry. Unlike enzymes involved in peptidoglycan metabolism, other surface proteins displayed uneven distribution in the mutants. A total of 13 LPXTG-containing proteins were identified exclusively in strains having a functional SrtA. In contrast, two surface proteins, Lmo2185 and Lmo2186, were identified only when SrtB was active. The analysis of the peptides identified in these proteins suggests that SrtB of L. monocytogenes may recognize two different sorting motifs, NXZTN and NPKXZ. Taken together, these data demonstrate that non-gel proteomics is a powerful technique to rapidly identify sortase substrates and to gain insights on potential sorting motifs.