Aims. We investigate the evolution of large- and small-scale magnetic fields in galaxies at high redshifts during the time of galaxy evolution. Methods. We use the dynamo theory to derive the timescales of amplification and ordering of magnetic fields in disk and puffy galaxies. Turbulence in protogalactic halos generated by thermal virialization can drive an efficient turbulent dynamo. Results from simulations of hierarchical structure formation cosmology provide a tool to develop an evolutionary model of regular magnetic fields coupled to galaxy formation and evolution. Results. The turbulent (small-scale) dynamo was able to amplify a weak seed magnetic field in halos of protogalaxies to a few microG strength within a few 10^8 yr. This turbulent field served as a seed for the mean-field (large-scale) dynamo. Galaxies similar to the Milky Way formed their disks at z~4 and regular fields of microG strength and a few kpc coherence length were generated within 2 Gyr (at z~3), but field ordering up to the coherence scale of the galaxy size took another 6 Gyr (at z~0.5). Giant galaxies formed their disk already at z~10, allowing more efficient dynamo generation of strong regular fields (with kpc coherence length) already at z~4. However, the age of the Universe is short to achieve fully coherent fields in giant galaxies larger than 15 kpc. Dwarf galaxies should have hosted fully coherent fields already at ~1. After a major merger the strength of the turbulent field is enhanced by a factor of a few. Conclusions. This evolutionary scenario can be tested by measurements of polarized synchrotron emission and Faraday rotation with the planned Square Kilometre Array (SKA). We predict an anticorrelation between galaxy size and coherence scale (abridged).