Infections by the Burkholderia cepacia complex (Bcc) remain seriously life threatening to cystic fibrosis (CF) patients, and no effective eradication is available. A vaccine to protect patients against Bcc infections is a highly attractive therapeutic option, but none is available. A strategy combining the bioinformatics identification of putative surface-exposed proteins with an experimental approach encompassing the “shaving” of surface-exposed proteins with trypsin followed by peptide identification by liquid chromatography and mass spectrometry is here reported. The methodology allowed the bioinformatics identification of 263 potentially surface-exposed proteins, 16 of them also experimentally identified by the “shaving” approach. Of the proteins identified, 143 have a high probability of containing B-cell epitopes that are surface-exposed. The immunogenicity of three of these proteins was demonstrated using serum samples from Bcc-infected CF patients and Western blotting, validating the usefulness of this methodology in identifying potentially immunogenic surface-exposed proteins that might be used for the development of Bcc-protective vaccines.