Candida albicans colonizes human mucosa and prosthetic surfaces associated with artificial joints, catheters, and dentures. In the oral cavity, C. albicans coexists with numerous bacterial species, and evidence suggests that bacteria may modulate fungal growth and biofilm formation. Streptococcus gordonii is found on most oral cavity surfaces and interacts with C. albicans to promote hyphal and biofilm formation. In this study, we investigated the role of the hyphal-wall protein Als3p in interactions of C. albicans with S. gordonii. Utilizing an ALS3 deletion mutant strain, it was shown that cells were not affected in initial adherence to the salivary pellicle or in hyphal formation in the planktonic phase. However, the Als3(-) mutant was unable to form biofilms on the salivary pellicle or deposited S. gordonii DL1 wild-type cells, and after initial adherence, als3Δ/als3Δ (ΔALS3) cells became detached concomitant with hyphal formation. In coaggregation assays, S. gordonii cells attached to, and accumulated around, hyphae formed by C. albicans wild-type cells. However, streptococci failed to attach to hyphae produced by the ΔALS3 mutant. Saccharomyces cerevisiae S150-2B cells expressing Als3p, but not control cells, supported binding of S. gordonii DL1. However, S. gordonii Δ(sspA sspB) cells deficient in production of the surface protein adhesins SspA and SspB showed >50% reduced levels of binding to S. cerevisiae expressing Als3p. Lactococcus lactis cells expressing SspB bound avidly to S. cerevisiae expressing Als3p, but not to S150-2B wild-type cells. These results show that recognition of C. albicans by S. gordonii involves Als3 protein-SspB protein interaction, defining a novel mechanism in fungal-bacterial communication.