We derive a Melvin universe-type solution describing a magnetic field permeating the whole universe in gravity minimally coupled to any nonlinear electromagnetic theory, including Born-Infeld theory. For a large set of nonlinear electrodynamics theories, our solution is complete and non-singular; as long as the magnetic field is sub-critical. We examine some properties of the solution; in particular, there is a shift of the symmetry axis and a nonstandard period along the orbits of the U(1) symmetry to avoid a conical singularity. We show these are consistent with the usual Dirac quantization condition for the magnetic flux. We find exact solutions describing propagation of waves in the 'generalized Melvin universe' along the principal null directions of the electromagnetic field, where the Boillat and Einstein lightcone touch. By electric-magnetic duality we show that similar Melvin electric and dyonic universes can be obtained.