We present the first self-consistent, three-dimensional (3D) core-collapse supernova simulations performed with the Prometheus-Vertex code for a rotating progenitor star. Besides using the angular momentum of the 15 solar-mass model as obtained in the stellar evolution calculation with an angular frequency of about 0.001 rad/s (spin period of more than 6000 s) at the Si/Si-O interface, we also computed 2D and 3D cases with no rotation and with a ~300 times shorter rotation period and different angular resolutions. In 2D, only the nonrotating and slowly rotating models explode, while rapid rotation prevents an explosion within 500 ms after bounce because of lower radiated neutrino luminosities and mean energies and thus reduced neutrino heating. In contrast, only the fast rotating model develops an explosion in 3D when the Si/Si-O interface collapses through the shock. The explosion becomes possible by the support of a powerful SASI spiral mode, which compensates for the reduced neutrino heating and pushes strong shock expansion in the equatorial plane. Fast rotation in 3D leads to a two-dimensionalization of the turbulent energy spectrum (yielding roughly a -3 instead of a -5/3 power-law slope at intermediate wavelengths) with enhanced kinetic energy on the largest spatial scales. We also introduce a generalization of the universal critical luminosity condition of Summa et al. (2016) to account for the effects of rotation, and demonstrate its viability for a set of more than 40 core-collapse simulations including 9 and 20 solar-mass progenitors as well as black-hole forming cases of 40 and 75 solar-mass stars to be discussed in forthcoming papers.