Abstract Climate change and variability can severely constrain the productivity of pastoral herds by reducing water availability, forage production and quality, and hence the carrying capacity of rangelands. In particular, the risk of heavy livestock losses suffered during recurrent severe droughts associated with climate change and variability presents one of the most serious threats to pastoral livestock keepers. To generate insights into how climate change and variability adversely affect cattle production in the Borana of southern Ethiopia, we analyzed perceptions of herders and long-term changes in cattle numbers and climate data. A total of 242 households were surveyed to generate data on perceived trends in climate, rangeland condition and livestock production. Socio-demographic characteristics of households and cattle mortality due to the 2010/2011 drought were also recorded. Using a local time calendar, cattle herd history was reconstructed for a period spanning five major droughts to portray the linkage between changes in cattle numbers and changes in rainfall and temperature. Most of the herders perceived that rainfall has become more unpredictable, less in amount and shorter in duration, while drought recurrence and temperature have increased. Similarly, the majority perceived a decreasing trend in cattle herd sizes and their production performances. The 2010/2011 drought was associated with a substantial decline in cattle herd sizes due to increased mortality (26%) and forced off-take (19%). Death occurrences and mortality rates varied significantly by district, herd size and feed supplementation. Spectral density analysis revealed a quasi-periodic pattern in the annual rainfall with an approximate cycle period of 8.4 years, suggesting that droughts recur approximately every 8.4 years. A downward trend in cattle population mirrored a similar underlying trend in the interannual rainfall variation. Accordingly, changes in cattle number were significantly linked with changes in rainfall. In conclusion, perceptions corroborated by empirical evidences showed that climate change and variability were associated with declining cattle numbers, portending a precarious future to the sustainability of cattle pastoralism in southern Ethiopia and other pastoral systems.