We establish probabilistic small data global well-posedness of the energy-critical Maxwell-Klein-Gordon equation relative to the Coulomb gauge for scaling super-critical random initial data. The proof relies on an induction on frequency procedure and a modified linear-nonlinear decomposition furnished by a delicate "probabilistic" parametrix construction. This is the first global existence result for a geometric wave equation for random initial data at scaling super-critical regularity.