The self-diffusion phenomenon in a two-dimensional dusty plasma at extremely strong (effective) magnetic fields is studied experimentally and by means of molecular dynamics simulations. In the experiment the high magnetic field is introduced by rotating the particle cloud and observing the particle trajectories in a corotating frame, which allows reaching effective magnetic fields up to 3000 T. The experimental results confirm the predictions of the simulations: (i) superdiffusive behavior is found at intermediate timescales and (ii) the dependence of the self-diffusion coefficient on the magnetic field is well reproduced.