Members of the Burkholderia cepacia complex (Bcc) cause chronic opportunistic lung infections in people with cystic fibrosis (CF), resulting in a gradual lung function decline and, ultimately, patient death. The Bcc is a complex of 20 species and is rarely eradicated once a patient is colonized; therefore, vaccination may represent a better therapeutic option. We developed a new proteomics approach to identify bacterial proteins that are involved in the attachment of Bcc bacteria to lung epithelial cells. Fourteen proteins were reproducibly identified by two-dimensional gel electrophoresis from four Bcc strains representative of two Bcc species: Burkholderia cenocepacia, the most virulent, and B. multivorans, the most frequently acquired. Seven proteins were identified in both species, but only two were common to all four strains, linocin and OmpW. Both proteins were selected based on previously reported data on these proteins in other species. Escherichia coli strains expressing recombinant linocin and OmpW showed enhanced attachment (4.2- and 3.9-fold) to lung cells compared to the control, confirming that both proteins are involved in host cell attachment. Immunoproteomic analysis using serum from Bcc-colonized CF patients confirmed that both proteins elicit potent humoral responses in vivo. Mice immunized with either recombinant linocin or OmpW were protected from B. cenocepacia and B. multivorans challenge. Both antigens induced potent antigen-specific antibody responses and stimulated strong cytokine responses. In conclusion, our approach identified adhesins that induced excellent protection against two Bcc species and are promising vaccine candidates for a multisubunit vaccine. Furthermore, this study highlights the potential of our proteomics approach to identify potent antigens against other difficult pathogens.