Extracellular fibrinogen-binding protein (Efb) from Staphylococcus aureus inhibits platelet activation, although its mechanism of action has not been established. In this study, we discovered that the N-terminal region of Efb (Efb-N) promotes platelet binding of fibrinogen and that Efb-N binding to platelets proceeds via two independent mechanisms: fibrinogen-mediated and fibrinogen-independent. By proteomic analysis of Efb-interacting proteins within platelets and confirmation by pulldown assays followed by immunoblotting, we identified P-selectin and multimerin-1 as novel Efb interaction partners. The interaction of both P-selectin and multimerin-1 with Efb is independent of fibrinogen. We focused on Efb interaction with P-selectin. Excess of P-selectin extracellular domain significantly impaired Efb binding by activated platelets, suggesting that P-selectin is the main receptor for Efb on the surface of activated platelets. Efb-N interaction with P-selectin inhibited P-selectin binding to its physiological ligand, P-selectin glycoprotein ligand-1 (PSGL-1), both in cell lysates and in cell-free assays. Because of the importance of P-selectin-PSGL-1 binding in the interaction between platelets and leukocytes, we tested human whole blood and found that Efb abolishes the formation of platelet-monocyte and platelet-granulocyte complexes. In summary, we present evidence that in addition to its documented antithrombotic activity, Efb can play an immunoregulatory role via inhibition of P-selectin-PSGL-1-dependent formation of platelet-leukocyte complexes.