We investigated the storage lower urinary tract symptoms (LUTS) before and after the first dose of coronavirus disease 2019 (COVID-19) vaccine and the association between pre-vaccinated overactive bladder (OAB) and the worsening of storage LUTS following COVID-19 vaccination. This cross-sectional study in a third-level hospital in Taiwan used the validated pre- and post-vaccinated Overactive Bladder Symptom Score (OABSS). Diagnosis of OAB was made using pre-vaccinated OABSS. The deterioration of storage LUTS was assessed as the increased score of OABSS following vaccination. Of 889 subjects, up to 13.4% experienced worsened storage LUTS after vaccination. OAB was significantly associated with an increased risk of worsening urinary urgency (p = 0.030), frequency (p = 0.027), and seeking medical assistance due to urinary adverse events (p < 0.001) after vaccination. The OAB group faced significantly greater changes in OABSS-urgency (p = 0.003), OABSS-frequency (p = 0.025), and total OABSS (p = 0.014) after vaccination compared to those observed in the non-OAB group. Multivariate regression revealed that pre-vaccinated OAB (p = 0.003) was a risk for the deterioration of storage LUTS. In conclusion, storage LUTS may deteriorate after vaccination. OAB was significantly associated with higher risk and greater changes in worsening storage LUTS. Storage LUTS should be closely monitored after COVID-19 vaccination, especially in those OAB patients.