Staphylococcus aureus and Staphylococcus epidermidis are the most important etiological agents of biofilm associated-infections on indwelling medical devices. Biofilm infections may also develop independently of indwelling devices, e.g., in native valve endocarditis, bone tissue, and open wounds. After attachment to tissue or indwelling medical devices that have been conditioned with host plasma proteins, staphylococcal biofilms grow, and produce a specific environment which provides the conditions for cell–cell interaction and formation of multicellular communities. Bacteria living in biofilms express a variety of macromolecules, including exopolysaccharides, proteins, extracellular eDNA, and other polymers. The S. aureus surface protein C and G (SasC and SasG), clumping factor B (ClfB), serine aspartate repeat protein (SdrC), the biofilm-associated protein (Bap), and the fibronectin/fibrinogen-binding proteins (FnBPA and FnBPB) are individually implicated in biofilm matrix formation. In S. epidermidis, a protein named accumulation-associated protein (Aap) contributes to both the primary attachment phase and the establishment of intercellular connections by forming fibrils on the cell surface. In S. epidermidis, proteinaceous biofilm formation can also be mediated by the extracellular matrix binding protein (Embp) and S. epidermidis surface protein C (SesC). Additionally, multifunctional proteins such as extracellular adherence protein (Eap) and extracellular matrix protein binding protein (Emp) of S. aureus and the iron-regulated surface determinant protein C (IsdC) of S. lugdunensis can promote biofilm formation in iron-depleted conditions. This multitude of proteins intervene at different stages of biofilm formation with certain proteins contributing to biofilm accumulation and others mediating primary attachment to surfaces. This review examines the contribution of proteins to biofilm formation in Staphylococci. The potential to develop vaccines to prevent protein-dependent biofilm formation during staphylococcal infection is discussed.