An important goal after structural genomics is to build up the structures of higher-order protein-protein complexes from structures of the individual subunits. Often structures of higher order complexes are difficult to obtain by crystallography. We have used an alternative approach in which the structures of the individual catalytic (C) subunit and RIalpha regulatory (R) subunit of PKA were first subjected to computational docking, and the top 100,000 solutions were subsequently filtered based on amide hydrogen/deuterium (H/2H) exchange interface protection data. The resulting set of filtered solutions forms an ensemble of structures in which, besides the inhibitor peptide binding site, a flat interface between the C-terminal lobe of the C-subunit and the A- and B-helices of RIalpha is uniquely identified. This holoenzyme structure satisfies all previous experimental data on the complex and allows prediction of new contacts between the two subunits.