Poly(butylene succinate) (PBS) is a biodegradable aliphatic polyester and is semicrystalline in nature. It has a wide range of engineering applications owing to its attractive combination of good processability and mechanical properties. PBS nanocomposites with graphene nanosheets (GNS) were prepared by melt compounding. We report on their thermal properties, GNS-initiated polymer crystallization behaviour and the morphological changes in them. The crystallization and melting behaviour of the PBS matrix in the presence of dispersed GNS were studied by Differential scanning calorimetry (DSC) and polarized optical microscopy (POM). The nucleating effect of the addition of 0.5 wt % GNS to PBS was clearly demonstrated. DSC nonisothermal crystallization studies showed a clear decrease in the half-time of crystallization with increasing GNS content in PBS/GNS nanocomposites. It was observed that the Ozawa parameter values for the nanocomposites were lower than for neat PBS, and this indicated that the crystal morphology was different. The storage modulus of the nanocomposites increased with the addition of GNS in comparison to neat PBS, whereas the glass-transition temperature was unaltered. Thus, our X-ray diffraction (XRD) and DSC studies have shown that the well dispersed graphene nanosheets act as nucleating agent for crystallization. Consequently, the mechanical properties of the composites have been substantially improved as evident from dynamic mechanical and static tensile tests.