We study chaotic rotations of a rigid ellipsoidal body due to the effects of gravitational torques, in the case where this body exhibits spin-orbit misalignment. After first deriving a simple model of a rigid ellipsoid of uniform mass distribution with principal axis of rotation directed slightly out of the orbital plane, we prove using the Melnikov method that this perturbation is sufficient to excite the ellipsoid to chaotically rotate for a circular orbit. We further verify this analytical result with numerical time series and Poincar´e sections for circular orbits. We then use numerical simulations to demonstrate that elliptical orbits provide further pathways to chaos. Our primary finding is that increasing the degree of spin-orbit misalignment will increase the prevalence of initial conditions leading to chaotic dynamics, for elliptical bodies on both circular and elliptical orbits. Indeed, our results suggest that chaotic rotation of elongated bodies exhibiting spin-orbit misalignment is somewhat common for large enough deviation of the principal axis of rotation from the normal to the orbital plane, provided the rigid body lacks rotational symmetry around its spin-axis and, furthermore, exhibits sufficiently small angular momentum so that the effects of gravitational torques are nontrivial.