The aim of this study was a comparison between PO4−3-P removal from sewage using zeolite as support medium in subsurface flow treatment wetlands (SSF TWs) operated with different oxidation-reduction potentials (ORPs). In addition, the zeolite’s phosphate adsorption characteristics were evaluated. For this, Two mesocosm SSF TWs were installed and operated during 504 d for the PO4−3-P adsorption from sewage: a) mesocosm SSF TW with natural zeolite (MTW-Z1) and b) mesocosm SSF TW with gravel (MTW-G1). Two ORPs was used in MTW-Z1 and MTW-G1: a) ORP-A, ORP >+50 mV, b) ORP-B, ORP <−50 mV. Furthermore, the adsorption characteristics were evaluated in batch assays (zeolite amount and particle size were studied) with different PO4−3-P initial concentrations. Regarding the mesocosm SSF TWs evaluation, the PO4−3-P removed from sewage by MTW-Z1 is between 20% and 50% significantly (p < 0.05) higher than the MTW-G1. At the same time, ORP-A, above +50 mV, significantly improves (p < 0.05), by 10% more, the PO4−3-P removal capacity from sewage. Regarding adsorption characteristics, maximum adsorption capacity determined by Langmuir kinetic was 0.03 mg PO4−3-P g−1 for initial concentrations of 10–15 mg PO4−3-P L−1. In the case of MTW-Z1 with ORPs A (>+50 mV) and B (<−50 mV), the zeolite maximum adsorption capacity was 0.3 mg PO4−3-P g−1. Therefore, the potential maximum adsorption capacity of natural zeolite used as a medium in SSF TWs with ORP conditions below −50 mV and above +50 mV can be increased until 10-fold regarding Langmuir adsorption kinetic.