Bifidobacteria are commensal microoganisms found in the gastrointestinal tract.Several strains have been attributed beneficial traits at local and systemic levels, through pathogen exclusion or immune modulation, among other benefits. This has promoted a growing industrial and scientific interest in bifidobacteria as probiotic supplements. However, the molecular mechanisms mediating this cross-talk with the human host remain unknown. High-throughput technologies, from functional genomics to transcriptomics, proteomics and interactomics coupled to the development of both in vitro and in vivo models to study the dynamics of the intestinal microbiota and their effects on host cells, have eased the identification of key molecules in these interactions. Numerous secreted or surface-associated proteins or peptides have been identified as potential mediators of bifidobacteria-host interactions and molecular cross-talk, directly participating in sensing environmental factors, promoting intestinal colonization or mediating a dialogue with mucosa-associated immune cells. On the other hand, bifidobacteria induce the production of proteins in the intestine, by epithelial or immune cells, and other gut bacteria, which are key elements in orchestrating interactions among bifidobacteria, gut microbiota and host cells. This review aims to give a comprehensive overview on proteinaceous molecules described and characterized to date, as mediators of the dynamic interplay between bifidobacteria and the human host, providing a framework to identify knowledge gaps and future research needs.