The purpose of this study was to determine for the first time whether V˙O2max could be predicted accurately and reliably from a treadmill-based perceptually regulated exercise test (PRET) incorporating a safer and more practical upper limit of RPE 15 (“Hard”) than used in previous investigations. Eighteen volunteers (21.7 ± 2.8 years) completed three treadmill PRETs (each separated by 48 h) and one maximal graded exercise test. Participants self-regulated their exercise at RPE levels 9, 11, 13 and 15 in a continuous and incremental fashion. Oxygen uptake (V˙O2) was recorded continuously during each 3 min bout. V˙O2 values for the RPE range 9–15 were extrapolated to RPE19 and RPE20 using regression analysis to predict individual V˙O2max scores. The optimal limits of agreement (LoA) between actual (48.0 ± 6.2 ml kg−1 min−1) and predicted scores were −0.6 ± 7.1 and −2.5 ± 9.4 ml.kg−1 min−1 for the RPE20 and RPE19 models, respectively. Reliability analysis for the V˙O2max predictions yielded LoAs of 1.6 ± 8.5 (RPE20) and 2.7 ± 9.4 (RPE19) ml kg−1 min−1 between trials 2 and 3. These findings demonstrate that (with practice) a novel treadmill-based PRET can yield predictions of V˙O2max that are acceptably reliable and valid amongst young, healthy, and active adults.