C. albicans binds various bacteria, including the oral commensal Streptococcus gordonii. Published reports documented the role of C. albicans Als3 and S. gordonii SspB in this interaction, and the importance of the Als N-terminal domain (NT-Als) in C. albicans adhesion. Here, we demonstrate that Als1 also binds S. gordonii. We also describe use of the NT-Als crystal structure to design mutations that precisely disrupt peptide-binding cavity (PBC) or amyloid-forming region (AFR) function in Als3. C. albicans displaying Als3 PBC mutant proteins showed significantly reduced binding to S. gordonii; mutation of the AFR did not affect the interaction. These observations present an enigma: the Als PBC binds free C termini of ligands, but the SspB C terminus is covalently linked to peptidoglycan and thus unavailable as a ligand. These observations and the predicted SspB elongated structure suggest that partial proteolysis of streptococcal cell wall proteins is necessary for recognition by Als adhesins.