We investigate the effects of thermonuclear reaction rate uncertainties on nova nucleosynthesis. One-zone nucleosynthesis calculations have been performed by adopting temperature-density-time profiles of the hottest hydrogen-burning zone (i.e., the region in which most of the nucleosynthesis takes place). We obtain our profiles from 7 different, recently published, hydrodynamic nova simulations covering peak temperatures in the range from Tpeak=0.145-0.418 GK. For each of these profiles, we individually varied the rates of 175 reactions within their associated errors and analyzed the resulting abundance changes of 142 isotopes in the mass range below A=40. In total, we performed 7350 nuclear reaction network calculations. We use the most recent thermonuclear reaction rate evaluations for the mass ranges A=1-20 and A=20-40. For the theoretical astrophysicist, our results indicate the extent to which nova nucleosynthesis calculations depend on presently uncertain nuclear physics input, while for the experimental nuclear physicist our results represent at least a qualitative guide for future measurements at stable and radioactive ion beam facilities. We find that present reaction rate estimates are reliable for predictions of Li, Be, C and N abundances in nova nucleosynthesis. However, rate uncertainties of several reactions have to be reduced significantly in order to predict more reliable O, F, Ne, Na, Mg, Al, Si, S, Cl and Ar abundances. Results are presented in tabular form for each adopted nova simulation.