The buildings’ surroundings’ environmental exposure conditions (e.g., orientation, location, altitude, distance from the sea, temperature, precipitation, presence of damp, exposure to prevailing winds, among others) have a considerable influence on the performance and durability of their envelope. Furthermore, the intensity of these conditions can vary significantly with the height of the building and, consequently, influence the degradation of different parts of the same building in different ways. In a tall building, the upper part is more prone to higher solar radiation levels, temperature variations, and exposure to wind–rain action. On the other hand, external elements at the bottom are more susceptible to high levels of pollution, especially in city centres. In this sense, the main purpose of this study was to analyse the degradation processes in buildings with different heights and understand whether the processes and maintenance requirements are statistically different. A sample of 203 natural stone claddings (NSC), located in Portugal, was used as case study. The sample was collected based on the diagnosis of the degradation condition of these claddings through in situ visual inspections. To predict the degradation process of NSC over time, a stochastic service life prediction model, based on Petri nets (PN), was implemented. This model allows evaluating the performance of NSC by encompassing the uncertainty of the future performance of the claddings. The results obtained through the degradation and maintenance models were compared with real case studies to highlight the real impact of buildings’ height subjected to environmental exposure conditions on the maintainability of NSC.