Recent experiments have revealed spectacular transport properties in semimetals, such as the large, non-saturating magnetoresistance exhibited by WTe 2 (ref.). Topological semimetals with massless relativistic electrons have also been predicted as three-dimensional analogues of graphene. These systems are known as Weyl semimetals, and are predicted to have a range of exotic transport properties and surface states, distinct from those of topological insulators. Here we examine the magneto-transport properties of NbP, a material the band structure of which has been predicted to combine the hallmarks of a Weyl semimetal with those of a normal semimetal. We observe an extremely large magnetoresistance of 850,000% at 1.85 K (250% at room temperature) in a magnetic field of up to 9 T, without any signs of saturation, and an ultrahigh carrier mobility of 5 × 10 6 cm 2 V â '1 s â '1 that accompanied by strong Shubnikov-de Haas (SdH) oscillations. NbP therefore presents a unique example of a material combining topological and conventional electronic phases, with intriguing physical properties resulting from their interplay.