Cytochrome c oxidase catalyses the terminal step of cellular respiration in eukaryotes and in many prokaryotes. This enzyme reduces molecular oxygen by means of a process coupled with proton pumping. Models for proton pumping activity in cytochrome c oxidase can be divided into two groups, which are still strongly debated to date: one in which haem a is the key player, and another where this role is covered by the oxygen reduction site. Current models share the fact of requesting, more or less explicitly, an ordered sequence of events. Here, we show that all the available subunit I structures of this enzyme can be clustered in four groups. Starting from these structural observations, and considering the large corpus of available experimental data and theoretical considerations, a simple four-state (stochastic) pump model is proposed. This model implies a series of characteristics that reflect the behavior of the real enzyme in a natural way, where strictly sequential models require ad hoc assumptions (e.g. slipping mechanisms). Our results suggest that the stochastic conformational coupling could be a mechanism for energy transduction used by the protein machines.