Application of the Luttinger theorem to the Kondo lattice YbRh2Si2 suggests that its large 4f derived Fermi surface (FS) in the paramagnetic (PM) regime should be similar in shape and volume to that of the divalent local-moment antiferromagnet (AFM) EuRh2Si2 in its PM regime. Here we show by angle-resolved photoemission spectroscopy that paramagnetic EuRh2Si2 has a large FS essentially similar to the one seen in YbRh2Si2 down to 1 K. In EuRh2Si2 the onset of AFM order below 24.5 K induces an extensive fragmentation of the FS due to Brillouin zone folding, intersection and resulting hybridization of the Fermi-surface sheets. Our results on EuRh2Si2 indicate that the formation of the AFM state in YbRh2Si2 is very likely also connected with similar changes in the FS, which have to be taken into account in the controversial analysis and discussion of anomalies observed at the quantum critical point in this system.