The complex rotational and translational Brownian motion of anisotropic particles depends on their shape and the viscoelasticity of their surroundings. Because of their strong optical scattering and chemical versatility, gold nanorods would seem to provide the ultimate probes of rheology at the nanoscale, but the suitably accurate orientational tracking required to compute rheology has not been demonstrated. Here we image single gold nanorods with a laser-illuminated dark-field microscope and use optical polarization to determine their three-dimensional orientation to better than one degree. We convert the rotational diffusion of single nanorods in viscoelastic polyethylene glycol solutions to rheology and obtain excellent agreement with bulk measurements. Extensions of earlier models of anisotropic translational diffusion to three dimensions and viscoelastic fluids give excellent agreement with the observed motion of single nanorods. We find that nanorod tracking provides a uniquely capable approach to microrheology and provides a powerful tool for probing nanoscale dynamics and structure in a range of soft materials.