This is the first of two papers dealing with the adsorption of Au and formation of Aun nanostructures (n = 1-4) on hematite (0001) surface and adsorption of CO thereon. The stoichiometric Fe-terminated (0001) surface of hematite 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 of the systems studied were examined for vertical and flattened configurations of Aun nanostructures adsorbed on the hematite surfaces. The flattened ones, which can be viewed as bilayer-like structures, were found energetically more favored than vertical ones. For both classes of structures the adsorption binding energy increases with the number of Au atoms in a structure. The adsorption of Aun induces charge rearrangement at the Aun/oxide contact which is reflected in work function changes. In most considered cases Aun adsorption increases the work function. A detailed analysis of the bonding electron charge is presented and the corresponding electron charge rearrangements at the contacts were quantified by a Bader charge analyses. The interaction of a CO molecule with the Aun nanostructures supported on α-Fe2O3 (0001) and the oxide support was studied. It is found that the CO adsorption binding to the hematite supported Aun structures is more than twice as strong as to the bare hematite surface. Analysis of the Bader charges on the atoms showed that in each case CO binds to the most positively charged (cationic) atom of the Aun structure. Changes in the electronic structure of the Aun species and of the oxide support, and their consequences for the interactions with CO, are discussed.