We consider the two-species Vicsek model (TSVM) consisting of two kinds of self-propelled particles, A and B, that tend to align with particles from the same species and to antialign with the other. The model shows a flocking transition that is reminiscent of the original Vicsek model: it has a liquid-gas phase transition and displays micro-phase-separation in the coexistence region where multiple dense liquid bands propagate in a gaseous background. The interesting features of the TSVM are the existence of two kinds of bands, one composed of mainly A particles and one mainly of B particles, the appearance of two dynamical states in the coexistence region: the PF (parallel flocking) state in which all bands of the two species propagate in the same direction, and the APF (antiparallel flocking) state in which the bands of species A and species B move in opposite directions. When PF and APF states exist in the low-density part of the coexistence region they perform stochastic transitions from one to the other. The system size dependence of the transition frequency and dwell times show a pronounced crossover that is determined by the ratio of the band width and the longitudinal system size. Our work paves the way for studying multispecies flocking models with heterogeneous alignment interactions.