Per- and polyfluoroalkyl substances (PFAS) are an emerging class of pervasive and harmful micropollutant. Next-generation sensors are necessary to detect PFAS at sub-nanomolar levels. Electrochemistry can measure analyte concentrations at sub-10 nM levels and offers a deployable platform; however, the lack of chemical reactivity of PFAS species requires electrode surface functionalization with a molecularly imprinted polymer (MIP). Previously, such sensors have required a well-characterized one-electron mediator (i.e., ferrocene carboxylic acid or ferrocene methanol) for detection. Natural waterways do not have an abundance of ferrocenyl compounds for quantification, implying that these mediators limit sensor practicality, deployability, and cost. Here, we take advantage of ambient oxygen present in river water to quantify one of the more harmful PFAS molecules, perfluorooctanesulfonate (PFOS), from 0 to 0.5 nM on a MIP-modified carbon substrate. Differential pulse voltammetry (DPV) and electrochemical impedance spectroscopy (EIS) generated calibration curves for PFOS in river water using oxygen as the mediator. Importantly, we show that electrochemical impedance spectroscopy is superior to voltammetric techniques: like ultramicroelectrodes, this technique can be used in low-conductivity matrices like river water with high reproducibility. Further, impedance provides a PFOS limit of detection of 3.4 pM. We also demonstrate that the common interferents humic acid and chloride do not affect the sensor signal. These results are a necessary step forward in developing deployable sensors that act as a first line of defense for detecting PFAS contamination at its earliest onset.