The atomic structure and properties of nanoparticulate Fe2O3 are characterized starting from its smallest Fe2O3 building unit through (Fe2O3)n clusters to nanometer-sized Fe2O3 particles. This is achieved by combining global structure optimizations at the density functional theory level, molecular dynamics simulations by employing tailored, ab initio parameterized interatomic potential functions and experiments. With the exception of nearly tetrahedral, adamantane-like (Fe2O3)2 small (Fe2O3)n clusters assume compact, virtually amorphous structures with little or no symmetry. For n = 2-5 (Fe2O3)n clusters consist mainly of two- and three-membered Fe-O rings. Starting from n = 5 they increasingly assume tetrahedral shape with the adamantane-like (Fe2O3)2 unit as the main building block. However, the small energy differences between different isomers of the same cluster-size make precise structural assignment for larger (Fe2O3)n clusters difficult. The tetrahedral morphology persists for Fe2O3 nanoparticles with up to 3 nm in diameter. Simulated crystallization of larger nanoparticles with diameters of about 5 nm demonstrates pronounced melting point depression and leads to formation of ε-Fe2O3 single crystals with hexagonal morphology. This finding is in excellent agreement with the results obtained for Fe2O3 nanopowders generated by laser vaporization and provides the first direct indication that ε-Fe2O3 may be thermodynamically the most stable phase in this size regime.