Women are at significant risk of heterosexually transmitted human immunodeficiency virus (HIV) infection, with the mucosal epithelium of the cervix and vagina serving as a major portal of entry. The cervicovaginal mucosa naturally harbors dynamic microflora composed predominantly of lactobacilli, which may be genetically modified to serve as a more efficient protective barrier against the heterosexual transmission of HIV. We selected a vaginal strain of Lactobacillus, L. jensenii 1153, for genetic modification to display surface-anchored anti-HIV proteins. Genomic sequencing analyses revealed that L. jensenii 1153 encodes several unique high-molecular-weight cell wall-anchored proteins with a C-terminal cell wall sorting LPQTG motif. In this report, we employed these proteins to express a surface-anchored two-domain CD4 (2D CD4) molecule in L. jensenii 1153. Our studies indicated that the C-terminal cell wall sorting signal LPQTG motif alone is insufficient to drive the surface expression of heterologous proteins, and the display of surface-anchored 2D CD4 molecules required native sequences of a defined length upstream of the unique C-terminal LPQTG cell wall sorting signal and the positively charged C terminus in a Lactobacillus-based expression system. The modified L. jensenii strain displayed 2D CD4 molecules that were uniformly distributed on bacterial surfaces. The surface-anchored 2D CD4 molecule was recognized by a conformation-dependent anti-CD4 antibody, suggesting that the expressed proteins adopted a native conformation. The establishment of this Lactobacillus-based surface expression system, with potential broad applicability, represents a major step toward developing an inexpensive yet durable approach to topical microbicides for the mitigation of heterosexual transmission of HIV and other mucosally transmitted viral pathogens.