Protocols for testing or exploiting quantum correlations-such as entanglement, Bell nonlocality, and Einstein-Podolsky-Rosen steering- generally assume a common reference frame between two parties. Establishing such a frame is resource-intensive, and can be technically demanding for distant parties. While Bell nonlocality can be demonstrated with high probability for a large class of two-qubit entangled states when the parties have one or no shared reference direction, the degree of observed nonlocality is measurement-orientation dependent and can be arbitrarily small. In contrast, we theoretically prove that steering can be demonstrated with 100% probability, for a larger class of states, in a rotationally-invariant manner, and experimentally demonstrate rotationally-invariant steering in a variety of cases. We also show, by comparing with the steering inequality of Cavalcanti et al. [J. Opt. Soc. Am. B 32, A74 (2015)], that the steering inequality we derive is the optimal rotationally invariant one for the case of two settings per side and two-qubit states having maximally mixed reduced (local) states.