The Faraday rotation effect, quantified by the rotation measure (RM), is a powerful probe of the large-scale magnetization of the Universe—tracing magnetic fields not only on galaxy and galaxy cluster scales but also in the intergalactic medium (IGM; referred to as RMIGM). The redshift dependence of the latter has extensively been explored with observations. It has also been shown that this relation can help to distinguish between different large-scale magnetization scenarios. We study the evolution of this RMIGM for different primordial magnetogenesis scenarios to search for the imprints of primordial magnetic fields (PMFs; magnetic fields originating in the early Universe) on the redshift-dependence of RMIGM. We use cosmological magnetohydrodynamic simulations for evolving PMFs during large-scale structure formation, coupled with the light-cone analysis to produce a realistic statistical sample of mock RMIGM images. We study the predicted behavior for the cosmic evolution of RMIGM for different correlation lengths of PMFs, and provide fitting functions for their dependence on redshifts. We compare these mock RM trends with the recent analysis of the the LOw-Frequency ARray RM Grid and find that large-scale-correlated PMFs should have (comoving) strengths ≲0.75 nG, if they originated during inflation with the scale-invariant spectrum and (comoving) correlation length of ∼19 h −1 cMpc or ≲30 nG if they originated during phase-transition epochs with the comoving correlation length of ∼1 h −1 cMpc. Our findings agree with previous observations and confirm the results of semi-analytical studies, showing that upper limits on the PMF strength decrease as their coherence scales increase.