Recovery of rare earth elements (REEs) from industrial wastewater has drawn great attention due to their potential environmental toxicity, as well as their high demand in modern technologies. In this study, we developed a magnetic composite based on the high surface area porous β-cyclodextrin polymer (P-CDP), namely P-CDP@Fe3O4. Both P-CDP and P-CDP@Fe3O4 rapidly sequester REEs such as Nd, Gd, Eu, and Y, reaching equilibrium in less than 10 min and fitting the Langmuir isotherm model with maximum adsorption capacities ranging from 7.76 to 9.59 mg/g at 25 °C when the highest initial concentration was 100 mg/L. Besides, the recovery of these REEs was not affected by competitive alkali, alkaline earth, and transition metal ions in model studies and industrial wastewater as revealed by the recovery efficiencies, which ranged from 62% to 100% indicating an excellent selectivity on both adsorbents. In addition, both adsorbents can be fully regenerated under mildly acidic conditions for at least five consecutive cycles. Moreover, P-CDP@Fe3O4 can be easily isolated by an external magnetic field which simplifies its synthesis and usability. It also overcomes the clogging and high backpressure issues of P-CDP, which facilitates its application for REEs recovery as compared with P-CDP. These characteristics demonstrate the promise of P-CDP and P-CDP@Fe3O4 for the pollution control and recovery of REEs.