Covariant density functional theory is used to study the effect of strong magnetic fields, up to the limit predicted for neutron stars (for magnetars $B \approx10^{18}$G), on nuclear structure. All new terms in the equation of motion resulting from time reversal symmetry breaking by the magnetic field and the induced currents, as well as axial deformation, are taken into account in a self-consistent fashion. For nuclei in the iron region of the nuclear chart it is found that fields in the order of magnitude of $10^{17}$G significantly affect bulk properties like masses and radii.