It is predicted that climate change will strongly affect plant distributions in high elevation “sky islands” of tropical Andes. Polylepis forests are a dominant element of the treeline throughout the Andes Cordillera in South America. However, little is known about the climatic factors underlying the current distribution of Polylepis trees and the possible effect of global climate change. The species Polylepis quadrijuga is endemic to the Colombian Eastern Cordillera, where it plays a fundamental ecological role in high-altitude páramo-forest ecotones. We sought to evaluate the potential distribution of P. quadrijuga under future climate change scenarios using ensemble modeling approaches. We conducted a comprehensive assessment of future climatic projections deriving from 12 different general circulation models (GCMs), four Representative Concentration Pathways (R) emissions scenarios, and two different time frames (2041–2060 and 2061–2080). Additionally, based on the future projections, we evaluate the effectiveness of the National System of Protected Natural Areas of Colombia (SINAP) and Páramo Complexes of Colombia (PCC) in protecting P. quadrijuga woodlands. Here, we compiled a comprehensive set of observations of P. quadrijuga and study them in connection with climatic and topographic variables to identify environmental predictors of the species distribution, possible habitat differentiation throughout the geographic distribution of the species, and predict the effect of different climate change scenarios on the future distribution of P. quadrijuga. Our results predict a dramatic loss of suitable habitat due to climate change on this key tropical Andean treeline species. The ensemble Habitat Suitability Modeling (HSM) shows differences in suitable scores among north and south regions of the species distribution consistent with differences in topographic features throughout the available habitat of P. quadrijuga. Future projections of the HSM predicted the Páramo complex “Sumapaz-Cruz Verde” as a major area for the long-term conservation of P. quadrijuga because it provides a wide range of suitable habitats for the different evaluated climate change scenarios. We provide the first set of priority areas to perform both in situ and ex situ conservation efforts based on suitable habitat projections.