Materials with high carrier mobility showing large magnetoresistance (MR) have recently received much attention because of potential applications in future high-performance magneto-electric devices. Here, we report on the discovery of an electron-hole-compensated half-Heusler semimetal LuPtBi that exhibits an extremely high electron mobility of up to 79000 cm2/Vs with a non-saturating positive MR as large as 3200% at 2 K. Remarkably, the mobility at 300 K is found to exceed 10500 cm2/Vs, which is among the highest values reported in three-dimensional bulk materials thus far. The clean Shubnikov-de Haas quantum oscillation observed at low temperatures and the first-principles calculations together indicate that the high electron mobility is due to a rather small effective carrier mass caused by the distinctive band structure of the crystal. Our finding provide a new approach for finding large, high-mobility MR materials by designing an appropriate Fermi surface topology starting from simple electron-hole-compensated semimetals.