Haem-copper oxidases are the terminal enzymes in both prokaryotic and eukaryotic respiratory chains. They catalyse the reduction of dioxygen to water and convert redox energy into a transmembrane electrochemical proton gradient during their catalytic activity. Haem-copper oxidases show substantial structure similarity, but spectroscopic and biochemical analyses indicate that these enzymes contain diverse prosthetic groups and use different substrates (i.e. cytochrome c or quinol). Owing to difficulties in membrane protein crystallization, there are no definitive structural data about the quinol oxidase physiological substrate-binding site(s). In the present paper, we propose an atomic structure model for the menaquinol:O2 oxidoreductase of Bacillus subtilis (QOx.aa3). Furthermore, a multistep computational approach is used to predict residues involved in the menaquinol/menaquinone binding within B. subtilis QOx.aa3 as well as those involved in quinol/quinone binding within Escherichia coli QOx.bo3. Two specific sequence motifs, R70GGXDX4RXQX3PX3FX[D/N/E/Q]X2HYNE97 and G159GSPX2GWX2Y169 (B. subtilis numbering), were highlighted within QOx from Bacillales. Specific residues within the first and the second sequence motif participate in the high- and low-affinity substrate-binding sites respectively. Using comparative analysis, two analogous motifs, R71GFXDX4RXQX8[Y/F]XPPHHYDQ101 and G163EFX3GWX2Y173 (E. coli numbering) were proposed to be involved in Enterobacteriales/Rhodobacterales/Rhodospirillales QOx high- and low-affinity quinol-derivative-binding sites. Results and models are discussed in the context of the literature.