© 2018 American Physical Society. The interplay between magnetism and superconductivity is one of the important subjects to investigate the pairing mechanism in novel superconductors. We have found a new coexistence between an antiferromagnetic order in the Fe sublattice and superconductivity of the FeAs-based EuFe2As2 superconductor in the pressure range from 2.4 to 3.0 GPa by Fe57 nuclear forward scattering (NFS) using a single-crystal sample. The magnetic state in the Fe sublattice changes to a new antiferromagnetic one with superconductivity from a stripe-type antiferromagnetic one observed in the normal conducting state at 2.7 GPa. Below the superconducting transition temperature, the temperature dependence of Fe57 NFS spectra reveals that the new antiferromagnetic order develops with the superconductivity. This nontrivial coupling of two ordered states in EuFe2As2 under pressure demonstrates a new and intriguing relationship between magnetism and superconductivity in Fe-based superconductors.