The adsorption of small Aun (n = 1-4) nanostructures on oxygen terminated α-Fe2O3(0001) surface was investigated using density functional theory in the generalized gradient approximation of Perdew-Burke-Ernzerhof (PBE) form with Hubbard correction U, accounting for strong electron correlations (PBE+U). The structural, energetic, and electronic properties were examined for two classes of the adsorbed Aun nanostructures with vertical and flattened configurations. Similarly to the Fe-terminated α-Fe2O3(0001) surface considered in Part I, the flattened configurations were found energetically more favored than vertical ones. The binding of Aun to the O-terminated surface is much stronger than to the Fe-termination. The adsorption bonding energy of Aun and the work function of the Aun/α-Fe2O3(0001) systems decrease with the increased number of Au atoms in a structure. All of the adsorbed Aun structures are positively charged. The bonding of CO molecules to the Aun structures is distinctly stronger than on the Fe-terminated surface; however, it is weaker than the binding to the bare O-terminated surface. The CO molecule binds to the Aun/α-Fe2O3(0001) system through a peripheral Au atom partly detached from the Aun structure. The results of this work indicate that the most energetically favored sites for adsorption of a CO molecule on the Aun/α-Fe2O3(0001) systems are atoms in the Au(0.5+) oxidation state.