Multiferroics are materials having two or more order parameters (for instance, magnetic, electric, or elastic) coexisting in the same phase. They have emerged as an important topic in condensed matter physics due to both their intriguing physical behaviors and a broad variety of novel physical applications they enable. Here, we report the results of comprehensive studies of the magnetoelectric (ME) effect in multiferroics with superparamagnetic and ferroelectric phases. On the example of a solid solution of PbFe1/2Ta1/2O3 with (PbMg1/3Nb2/3O3)0.7(PbTiO3)0.3 or Pb(ZrTi)O3, we demonstrate that, in the system with the coexistent superparamagnetic and ferroelectric phases, the ME coefficient can be increased up to three orders in magnitude as compared to conventional magnetoelectrics. This is supported by both theoretical calculations and direct measurements of the ME coefficient. Our study demonstrates that multiferroics with superparamagnetic and ferroelectric phases can be considered as promising materials for applications along with composite multiphase (ferroelectric/ferromagnetic) structures.