The origin of astrophysical magnetic fields observed in galaxies and clusters of galaxies is still unclear. One possibility is that primordial magnetic fields generated in the early Universe provide seeds that grow through compression and turbulence during structure formation. A cosmological magnetic field present prior to recombination would produce substantial matter clustering at intermediate/small scales, on top of the standard inflationary power spectrum. In this work we study the effect of this alteration on one particular cosmological observable, cosmic shear. We adopt the semi-analytic halo model in order to describe the non-linear clustering of matter, and feed it with the altered mass variance induced by primordial magnetic fields...