Open clusters have been the focus of several exoplanet surveys, but only a few planets have so far been discovered. The Kepler spacecraft revealed an abundance of small planets around small cool stars, therefore, such cluster members are prime targets for exoplanet transit searches. Kepler's new mission, K2, is targeting several open clusters and star-forming regions around the ecliptic to search for transiting planets around their low-mass constituents. Here, we report the discovery of the first transiting planet in the intermediate-age (800 Myr) Beehive cluster (Praesepe). K2-95 is a faint (Kp = 15.5 mag) M3.0 +/- 0.5 dwarf from K2's Campaign 5 with an effective temperature of 3471 +/- 124 K, approximately solar metallicity and a radius of 0.402 +/- 0.050 R-circle dot. We detected a transiting planet with a radius of 3.47(-0.53)(+0.78)R(circle plus) and an orbital period of 10.134 days. We combined photometry, medium/high-resolution spectroscopy, adaptive optics/speckle imaging, and archival survey images to rule out any false-positive detection scenarios, validate the planet, and further characterize the system. The planet's radius is very unusual as M-dwarf field stars rarely have Neptune-sized transiting planets. The comparatively large radius of K2-95b is consistent with the other recently discovered cluster planets K2-25b (Hyades) and K2-33b (Upper Scorpius), indicating systematic differences in their evolutionary states or formation. These discoveries from K2 provide a snapshot of planet formation and evolution in cluster environments and thus make excellent laboratories to test differences between field-star and cluster planet populations.