The rotational band structure of the Z ¼ 104 nucleus 256Rf has been observed up to a tentative spin of 20@ using state-of-the-art -ray spectroscopic techniques. This represents the first such measurement in a superheavy nucleus whose stability is entirely derived from the shell-correction energy. The observed rotational properties are compared to those of neighboring nuclei and it is shown that the kinematic and dynamic moments of inertia are sensitive to the underlying single-particle shell structure and the specific location of high-j orbitals. The moments of inertia therefore provide a sensitive test of shell structure and pairing in superheavy nuclei which is essential to ensure the validity of contemporary nuclear models in this mass region. The data obtained show that there is no deformed shell gap at Z ¼ 104, which is predicted in a number of current self-consistent mean-field models.