Current regimens for the detection and surveillance of bladder cancer are invasive and have suboptimal sensitivity. Here, we present a novel high-throughput sequencing (HTS) method for detection of urine tumor DNA (utDNA) called utDNA CAPP-Seq (uCAPP-Seq) and apply it to 67 healthy adults and 118 patients with early-stage bladder cancer who had urine collected either prior to treatment or during surveillance. Using this targeted sequencing approach, we detected a median of 6 mutations per patient with bladder cancer and observed surprisingly frequent mutations of the PLEKHS1 promoter (46%), suggesting these mutations represent a useful biomarker for detection of bladder cancer. We detected utDNA pretreatment in 93% of cases using a tumor mutation-informed approach and in 84% when blinded to tumor mutation status, with 96% to 100% specifi city. In the surveillance setting, we detected utDNA in 91% of patients who ultimately recurred, with utDNA detection preceding clinical progression in 92% of cases. uCAPP-Seq outperformed a commonly used ancillary test (UroVysion, P = 0.02) and cytology and cystoscopy combined (P ≤ 0.006), detecting 100% of bladder cancer cases detected by cytology and 82% that cytology missed. Our results indicate that uCAPP-Seq is a promising approach for early detection and surveillance of bladder cancer.