Charged particles can be accelerated to high energies by collisionless shock waves in astrophysical environments, such as supernova remnants. By interacting with the magnetized ambient medium, these shocks can transfer energy to particles. Despite increasing efforts in the characterization of these shocks from satellite measurements at the Earths bow shock and powerful numerical simulations, the underlying acceleration mechanism or a combination thereof is still widely debated. Here, we show that astrophysically relevant super-critical quasi-perpendicular magnetized collisionless shocks can be produced and characterized in the laboratory. We observe characteristics of super-criticality in the shock profile as well as the energization of protons picked up from the ambient gas to hundreds of keV. Kinetic simulations modelling the laboratory experiment identified shock surfing as the proton acceleration mechanism. Our observations not only provide the direct evidence of early stage ion energization by collisionless shocks, but they also highlight the role this particular mechanism plays in energizing ambient ions to feed further stages of acceleration. Furthermore, our results open the door to future laboratory experiments investigating the possible transition to other mechanisms, when increasing the magnetic field strength, or the effect induced shock front ripples could have on acceleration processes.