Cyclic dominance of species has been identified as a potential mechanism to maintain biodiversity, see, e.g., B. Kerr, M. A. Riley, M. W. Feldman and B. J. M. Bohannan Nature 418, 171 (2002)] and B. Kirkup and M. A. Riley Nature 428, 412 (2004)]. Through analytical methods supported by numerical simulations, we address this issue by studying the properties of a paradigmatic non-spatial three-species stochastic system, namely, the "rock-paper-scissors" or cyclic Lotka-Volterra model. While the deterministic approach (rate equations) predicts the coexistence of the species resulting in regular (yet neutrally stable) oscillations of the population densities, we demonstrate that fluctuations arising in the system with a finite number of agents drastically alter this picture and are responsible for extinction: After long enough time, two of the three species die out. As main findings we provide analytic estimates and numerical computation of the extinction probability at a given time. We also discuss the implications of our results for a broad class of competing population systems.