We studied phase separation in the single-crystalline antiferromagnetic superconductor Rb₂Fe₄Se₅ (RFS) using a combination of scattering-type scanning near-field optical microscopy and low-energy muon spin rotation (LE-μSR). We demonstrate that the antiferromagnetic and superconducting phases segregate into nanometer-thick layers perpendicular to the iron-selenide planes, while the characteristic in-plane size of the metallic domains reaches 10μm. By means of LE-μSR we further show that in a 40-nm thick surface layer the ordered antiferromagnetic moment is drastically reduced, while the volume fraction of the paramagnetic phase is significantly enhanced over its bulk value. Self-organization into a quasiregular heterostructure indicates an intimate connection between the modulated superconducting and antiferromagnetic phases.