Cosmological and astrophysical observations over the years have revealed that our universe is magnetized on various length scales. In this talk, I will discuss how cosmological magnetic fields can be used to probe fundamental physics. I will first review the observational status of the magnetic fields in our universe. Next, I will show the need for physics beyond the Standard Model to explain the origin of the magnetic fields, by refuting the long-standing claim that the Weyl anomaly of quantum electrodynamics can produce seed magnetic fields in the early universe. I will then describe efforts to build models of magnetic field generation within beyond-the-Standard-Model physics, as well as the challenges such as the saturation due to the Schwinger process. Finally, I will introduce recent ideas for overcoming the difficulties and obtaining a comprehensive theory of our magnetized universe.