The emergence of antibiotic-resistant bacteria is a major public health threat, and therefore novel antimicrobial targets and strategies are urgently needed. In this regard, cell-wall-associated proteases are envisaged as interesting antimicrobial targets due to their role in cell wall remodeling. Here, we describe the discovery and characteristics of a protease substrate that is processed by a bacterial cell-wall-associated protease. Stationary-phase grown Gram-positive bacteria were incubated with fluorogenic protease substrates, and their cleavage and covalent incorporation into the cell wall was analyzed. Of all of the substrates used, only one substrate, containing a valine–leucine–lysine (VLK) motif, was covalently incorporated into the bacterial cell wall. Linkage of the VLK-peptide substrate appeared unrelated to sortase A and B activity, as both wild-type and sortase A and B knock out Staphylococcus aureus strains incorporated this substrate into their cell wall with comparable efficiency. Additionally, the VLK-peptide substrate showed significantly higher incorporation in the cell wall of VanA-positive Enterococcus faecium strains than in VanB- and vancomycin-susceptible isolates. In conclusion, the VLK-peptide substrate identified in this study shows promise as a vehicle for targeting antimicrobial compounds and diagnostic contrast agents to the bacterial cell wall.