To monitor the docking site for cytochrome c on cytochrome oxidase from Paracoccus denitrificans, a series of site-directed mutants in acidic residues exposed on the three largest subunits was constructed, and the purified enzymes were assayed for their steady-state kinetic parameters, their ionic strength dependence, and their fast electron entry kinetics by stopped-flow measurements. Increasing the ionic strength, the maximum of the bell-shaped dependence of the steady-state rate observed for wild type shifts the maximum to lower ionic strength in most of the mutants. The Km determined in steady-state experiments under different conditions is largely increased for most of the subunit II and one of the subunit I mutants, giving evidence that binding is impaired, whereas subunit III residues do not seem to contribute significantly. In addition, the bimolecular rate constant for cytochrome c oxidation under pre-steady state conditions was measured using stopped flow spectroscopy. Taken together, the results demonstrate that the initial interaction of cytochrome c and oxidase is mediated through glutamates and aspartates mainly located in subunit II. The crystal structure of oxidase reveals that the participating residues are clustered, creating an extended, negatively charged patch. We propose this clustering to be a decisive factor in the recognition of positively charged patches on the surface of cytochrome c.