Transient absorption microscopy is used to examine the breathing modes of single gold nanowires in highly viscous liquids. By performing measurements on the same wire in air and liquid, the damping contribution from the liquid can be separated from the intrinsic damping of the nanowire. The results show that viscous liquids strongly reduce the vibrational lifetimes, but not to the extent predicted by standard models for nanomaterial-liquid interactions. To explain these results a general theory for compressible viscoelastic fluid-structure interactions is developed. The theory results are in good agreement with experiment, which confirms that compressible non-Newtonian flow phenomena are important for vibrating nanostructures. This is the first theoretical study and experimental measurement of the compressible viscoelastic properties of simple liquids.