Wastewater-based epidemiology (WBE) is a promising approach for estimating population-wide COVID-19 prevalence through detection of severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) RNA in wastewater. However, various methodological challenges associated with WBE would affect the accuracy of prevalence estimation. To date, the overall uncertainty of WBE and the impact of each step on the prevalence estimation are largely unknown. This study divided the WBE approach into five steps (i.e., virus shedding; in-sewer transportation; sampling and storage; analysis of SARS-CoV-2 RNA concentration in wastewater; back-estimation) and further summarized and quantified the uncertainties associated with each step through a systematic review. Although the shedding of SARS-CoV-2 RNA varied greatly between COVID-19 positive patients, with more than 10 infected persons in the catchment area, the uncertainty caused by the excretion rate became limited for the prevalence estimation. Using a high-frequency flow-proportional sampling and estimating the prevalence through actual water usage data significantly reduced the overall uncertainties to around 20–40% (relative standard deviation, RSD). And under such a scenario, the analytical uncertainty of SARS-CoV-2 RNA in wastewater was the dominant factor. This highlights the importance of using surrogate viruses as internal or external standards during the wastewater analysis, and the need for further improvement on analytical approaches to minimize the analytical uncertainty. This study supports the application of WBE as a complementary surveillance strategy for monitoring COVID-19 prevalence and provides methodological improvements and suggestions to enhance the reliability for future studies.