From the 1st of February 2018 codeine was rescheduled from an over-the-counter (OTC) to a prescription only medicine in Australia to reduce harms from its misuse. This study used wastewater-based epidemiology to evaluate changes in codeine consumption at the population level, before and after rescheduling. We analysed 3,703 wastewater samples from up to 48 wastewater treatment plants, between August 2016 and August 2019. Samples represented a total of 10 million people, 45% of the Australian population, and were collected from state capitals and regional areas in each state or territory of Australia. Codeine concentrations were determined by Liquid Chromatography Mass Spectrometry and converted to per-capita consumption estimates using the site flows, populations and codeine excretion kinetics. Average per-capita consumption of codeine in each state or territory decreased immediately following the change, with significantly lower consumption rates in all states. Population-weighted average codeine consumption decreased at the national level by approximately 40% over the period of sampling. Over the same period the total amount of codeine prescribed under the Pharmaceutical Benefits Scheme (PBS) showed negligible change, suggesting that a decline in OTC codeine accounted for the majority of the decrease. Following the rescheduling, seasonal use of codeine also decreased, with a smaller difference in use between summer and winter periods post change. Results suggest regulating codeine clearly resulted in an immediate and substantial decrease in codeine consumption in all regions of Australia and that wastewater-based epidemiology is a unique tool for assessing such changes.