When graphene is placed on a crystalline surface, the periodic structures within the layers superimpose and moiré superlattices form. Small lattice rotations between the two materials in contact strongly modify the moiré lattice parameter, upon which many electronic, vibrational, and chemical properties depend. While precise adjustment of the relative orientation in the degree- and sub-degree-range can be achieved via careful deterministic transfer of graphene, we report on the spontaneous reorientation of graphene on a metallic substrate, Ir(111). We find that selecting a substrate temperature between 1530 and 1000 K during the growth of graphene leads to distinct relative rotational angles of 0°, ± 0.6°, ±1.1°, and ±1.7°. When modeling the moiré superlattices as two-dimensional coincidence networks, we can ascribe the observed rotations to favorable low-strain graphene structures. The dissimilar thermal expansion of the substrate and graphene is regarded as an effective compressive biaxial pressure that is more easily accommodated in graphene by small rotations rather than by compression.