Primordial magnetic fields (PMFs) offer a simple explanation for the origin of galactic magnetic fields as well as of the purportedly detected magnetic fields in cosmic voids. In the talk, I will show how PMFs' influence on structure formation on<Mpc scales can offer a complementary method to test for their existence. On scales relevant to galaxies and black holes, I show that PMFs can significantly enhance the baryon fraction in halos as well as the abundance of halos. Next, I show that on scales below the Baryon Jeans scales, PMFs can enhance the dark matter power spectrum purely by gravitational influence. I conclude by arguing how the search for dark matter minihalos can potentially provide the most sensitive probe for PMFs.