The cluster Praesepe (age 650 Myr) is an ideal laboratory to study stellar evolution. Specifically, it allows us to trace the long-term decline of rotation and activity on the main-sequence. Here we present rotation periods measured for five stars in Praesepe with masses of 0.1-0.5Ms -- the first rotation periods for members of this cluster. Photometric periodicities were found from two extensive monitoring campaigns, and are confirmed by multiple independent test procedures. We attribute these variations to magnetic spots co-rotating with the objects, thus indicating the rotation period. The five periods, ranging from 5 to 84h, show a clear positive correlation with object mass, a trend which has been reported previously in younger clusters. When comparing with data for F-K stars in the coeval Hyades, we find a dramatic drop in the periods at spectral type K8-M2 (corresponding to 0.4-0.6Ms). A comparison with periods of VLM stars in younger clusters provides a constraint on the spin-down timescale: We find that the exponential rotational braking timescale is clearly longer than 200 Myr, most likely 400-800 Myr. These results are not affected by the small sample size in the rotation periods. Both findings, the steep drop in the period-mass relation and the long spin-down timescale, indicate a substantial change in the angular momentum loss mechanism for very low mass objects, possibly the breakdown of the solar-type (Skumanich) rotational braking. While the physical origin for this behaviour is unclear, we argue that parts of it might be explained by the disappearance of the radiative core and the resulting breakdown of an interface-type dynamo in the VLM regime. Rotational studies in this mass range hold great potential to probe magnetic properties and interior structure of main-sequence stars.