There is growing evidence of escalating wildlife losses worldwide. Extreme wildlife losses have recently been documented for large parts of Africa, including western, Central and Eastern Africa. Here, we report extreme declines in wildlife and contemporaneous increase in livestock numbers in Kenya rangelands between 1977 and 2016. Our analysis uses systematic aerial monitoring survey data collected in rangelands that collectively cover 88% of Kenya’s land surface. Our results show that wildlife numbers declined on average by 68% between 1977 and 2016. The magnitude of decline varied among species but was most extreme (72–88%) and now severely threatens the population viability and persistence of warthog, lesser kudu, Thomson’s gazelle, eland, oryx, topi, hartebeest, impala, Grevy’s zebra and waterbuck in Kenya’s rangelands. The declines were widespread and occurred in most of the 21 rangeland counties. Likewise to wildlife, cattle numbers decreased (25.2%) but numbers of sheep and goats (76.3%), camels (13.1%) and donkeys (6.7%) evidently increased in the same period. As a result, livestock biomass was 8.1 times greater than that of wildlife in 2011–2013 compared to 3.5 times in 1977–1980. Most of Kenya’s wildlife (ca. 30%) occurred in Narok County alone. The proportion of the total “national” wildlife population found in each county increased between 1977 and 2016 substantially only in Taita Taveta and Laikipia but marginally in Garissa and Wajir counties, largely reflecting greater wildlife losses elsewhere. The declines raise very grave concerns about the future of wildlife, the effectiveness of wildlife conservation policies, strategies and practices in Kenya. Causes of the wildlife declines include exponential human population growth, increasing livestock numbers, declining rainfall and a striking rise in temperatures but the fundamental cause seems to be policy, institutional and market failures. Accordingly, we thoroughly evaluate wildlife conservation policy in Kenya. We suggest policy, institutional and management interventions likely to succeed in reducing the declines and restoring rangeland health, most notably through strengthening and investing in community and private wildlife conservancies in the rangelands.