Electron transfer between the water-soluble cytochrome c and the integral membrane protein cytochrome c oxidase (COX) is the terminal reaction in the respiratory chain. The first step in this reaction is the diffusional association of cytochrome c toward COX, and it is still not completely clear whether cytochrome c diffuses in the bulk solution while encountering COX, or whether it prefers to diffuse laterally on the membrane surface. This is a rather crucial question, since in the latter case the association would be strongly dependent on the lipid composition and the presence of additional membrane proteins. We applied Brownian dynamics simulations to investigate the effect of an atomistically modeled dipalmitoyl phosphatidylcholine membrane on the association behavior of cytochrome c toward COX from Paracoccus denitrificans. We studied the negatively charged, physiological electron-transfer partner of COX, cytochrome c(552), and the positively charged horse-heart cytochrome c. As expected, both cytochrome c species prefer diffusion in bulk solution while associating toward COX embedded in a membrane, where the partial charges of the lipids were switched off, and the corresponding optimal association pathways largely overlap with the association toward fully solvated COX. Remarkably, after switching on the lipid partial charges, both cytochrome c species were strongly attracted by the inhomogeneous charge distribution caused by the zwitterionic lipid headgroups. This effect is particularly enhanced for horse-heart cytochrome c and is stronger at lower ionic strength. We therefore conclude that in the presence of a polar or even a charged membrane, cytochrome c diffuses laterally rather than in three dimensions.