The melt crystallization of poly(vinyl alcohol) (PVA) and PVA composites has been a controversial subject due to inconclusive evidence and different opinions for its decomposition during crystallization. Using graphene as a model, the melt crystallization of PVA and PVA-graphene composites occurring during single-cycle and multiple-cycle non-isothermal annealing processes was systematically analyzed using different characterization techniques. The results obtained using single-cycle non-isothermal annealing indicated that the entire crystallization process took place through two main stages. The graphene in the PVA matrix regulates the nucleation and crystal growth manner of the PVA, yet resulting in retardation of the entire crystallization. The FTIR and Raman spectroscopic results particularly demonstrated that the annealing process not only improved the crystallinity but also led to clear decomposition in PVA and PVA-graphene composites, such as the elimination of hydroxyl groups and the production of C=C double bonds. The newly produced C=C double bonds were found to be responsible for the retardation of PVA macromolecule crystallization and the breaking of hydrogen bonds among the hydroxyl groups in the PVA chains. In addition, the morphological observation and multi-cycle non-isothermal crystallization further confirmed the existence of decomposition based on the surface damage as well as decreased crystallization enthalpy and crystallization peak temperature. Therefore, the non-isothermal crystallizations of the pure PVA and the PVA-graphene composites were in fact the combination of non-isothermal crystallization and non-isothermal degradation processes.