We generalize the original majority-vote (MV) model from two states to arbitrary p states and study the order-disorder phase transitions in such a p-state MV model on complex networks. By extensive Monte Carlo simulations and a mean-field theory, we show that for p≥3 the order of phase transition is essentially different from a continuous second-order phase transition in the original two-state MV model. Instead, for p≥3 the model displays a discontinuous first-order phase transition, which is manifested by the appearance of the hysteresis phenomenon near the phase transition. Within the hysteresis loop, the ordered phase and disordered phase are coexisting, and rare flips between the two phases can be observed due to the finite-size fluctuation. Moreover, we investigate the type of phase transition under a slightly modified dynamics [Melo et al., J. Stat. Mech. (2010) P110321742-546810.1088/1742-5468/2010/11/P11032]. We find that the order of phase transition in the three-state MV model depends on the degree heterogeneity of networks. For p≥4, both dynamics produce the first-order phase transitions.