(1) Background: Increased arterial stiffness is associated with cardiovascular (CV) diseases in end-stage renal disease (ESRD) patients, and CV mortality remains higher in kidney transplantation (KT) recipients compared to in the general population. KT is associated with an improvement in arterial stiffness in the early post-transplant period, followed by a potential re-worsening in the late period. In a cohort of KT patients, we evaluated the associations of pulse-wave velocity (PWV) measured at different time-points (pre-transplant, and early and late post-transplant periods) with CV morbi-mortality, as well as the evolution between these measurements with CV morbi-mortality. (2) Methods: Forty KT recipients with a 10-year follow-up were included. The association of PWV with CV events was assessed with multivariable cox analysis. Backward linear regressions were conducted to identify the determinants of PWV at 1 year and those of the long-term evolution of PWV after KT (delta PWV at 1 year—latest PWV). (3) Results: The absence of arterial stiffening during the long-term follow-up after KT is associated with a lower CV outcome rate (HR for the delta PWV = 0.76 (0.58–0.98), p = 0.036). Age at KT is associated with the worsening of arterial stiffness in the late post-transplantation period (β for the delta PWV = −0.104, p = 0.031). A high PWV at 1 year was associated with a potential for recovery during follow-up (β = 0.744, p < 0.0001). (4) Conclusions: The absence of PWV worsening in the late post-transplantation period was significantly associated with a lower risk of CV events, whereas early changes in PWV were not. Finding an intervention capable of reducing long-term PWV could improve the prognosis of KT recipients.