Lactobacilli have long been regarded as important constituents of the healthy human vagina. Lactobacillus iners is the most frequently detected bacterial species in the vagina, but little is known about its characteristics. We report a description of the whole-genome sequence of L. iners AB-1 along with comparative analysis of published genomes of closely related strains of lactobacilli. The genome is the smallest Lactobacillus reported to date, with a 1.3-Mbp single chromosome. The genome seems to have undergone one or more rapid evolution events that resulted in large-scale gene loss and horizontal acquisition of a number of genes for survival in the vagina. L. iners may exhibit specialized adaptation mechanisms to the vaginal environment, such as an iron-sulfur cluster assembly system, and several unique σ factors to regulate gene transcription in this fluctuating environment. A potentially highly expressed homolog of a cholesterol-binding lysin may also contribute to host cell adhesion or act as a defense mechanism against other microbes. Notably, there is a lack of apparent adhesion proteins, but several cell-anchor proteins were identified and may be important for interaction with the host mucosal tissues. L. iners is widely present in healthy females as well as those suffering from bacterial vaginosis or who have undergone antimicrobial therapy, suggesting that it is an important indigenous species of the vagina.