Lactobacillus johnsonii NCC 533 is a member of the acidophilus group of intestinal lactobacilli that has been extensively studied for their “probiotic” activities that include, pathogen inhibition, epithelial cell attachment, and immunomodulation. To gain insight into its physiology and identify genes potentially involved in interactions with the host, we sequenced and analyzed the 1.99-Mb genome of L. johnsonii NCC 533. Strikingly, the organism completely lacked genes encoding biosynthetic pathways for amino acids, purine nucleotides, and most cofactors. In apparent compensation, a remarkable number of uncommon and often duplicated amino acid permeases, peptidases, and phosphotransferase-type transporters were discovered, suggesting a strong dependency of NCC 533 on the host or other intestinal microbes to provide simple monomeric nutrients. Genome analysis also predicted an abundance (>12) of large and unusual cell-surface proteins, including fimbrial subunits, which may be involved in adhesion to glycoproteins or other components of mucin, a characteristic expected to affect persistence in the gastrointestinal tract (GIT). Three bile salt hydrolases and two bile acid transporters, proteins apparently critical for GIT survival, were also detected. In silico genome comparisons with the >95% complete genome sequence of the closely related Lactobacillus gasseri revealed extensive synteny punctuated by clear-cut insertions or deletions of single genes or operons. Many of these regions of difference appear to encode metabolic or structural components that could affect the organisms competitiveness or interactions with the GIT ecosystem.