To understand how proteins perform their function, knowledge about their structure and dynamics is essential. Here we use a combination of an efficient chemical lysine acetylation reaction and nanoLC-MALDI tandem mass spectrometry to probe the accessibility of every lysine residue in a protein complex. To demonstrate the applicability of this approach, we studied the interaction between the DNase domain of Colicin E9 (E9) and its immunity protein Im9. Free E9 and E9 in complex with Im9 were rapidly acetylated, followed by proteolytic digestion and analysis by LC-MALDI-TOF/TOF MS/MS. Acetylated peptides could be filtered out of the complex peptide mixtures using selective ion chromatograms of the specific immonium marker ions. Additionally, isobaric acetylated peptides, acetylated at different sites, could be separated by their LC retention times. The combination of LC and MALDI-TOF/TOF MS/MS provided information about the amount of acetylation on each individual lysine even for peptides containing several lysine residues. In general, our data agree well with those derived from the crystal structure of E9 and the E9:Im9 complex. Interestingly, next to in the binding interface expected lysines, K89 and K97, two from the crystal structure data unexpected lysines, K81 and K76, were observed to become less exposed upon Im9 binding. Moreover, K55 and K63, positioned in the predicted DNA binding region, were also found to be less accessible upon Im9 binding. These findings may illustrate some of the described differences in the solution-phase structure of the E9:Im9 complex compared with the crystal structure.