In this study, ceria-yttria co-stabilized zirconia (CYSZ) free-standing coatings, deposited by air plasma spraying (APS), were isothermally annealed at 1315 °C in order to explore the effect of sintering on the microstructure and the mechanical properties (i.e., hardness and Young's modulus). To this aim, coating microstructure, before and after heat treatment, was analyzed using scanning electron microscopy, and image analysis was carried out in order to estimate porosity fraction. Moreover, Vickers microindentation and depth-sensing nanoindentation tests were performed in order to study the evolution of hardness and Young's modulus as a function of annealing time. The results showed that thermal aging of CYSZ coatings leads to noticeable microstructural modifications. Indeed, the healing of finer pores, interlamellar, and intralamellar microcracks was observed. In particular, the porosity fraction decreased from ~10 to ~5% after 50 h at 1315 °C. However, the X-ray diffraction analyses revealed that high phase stability was achieved, as no phase decomposition occurred after thermal aging. In turn, both the hardness and Young's modulus increased, in particular, the increase in stiffness (with respect to "as produced" samples) was equal to ~25%, whereas the hardness increased to up to ~60%.