The equilibrium dynamics of a spherical particle immersed in a complex Maxwell fluid is analyzed in terms of velocity autocorrelation function (VACF), mean-square displacement (MSD), and power spectral density (PSD). We elucidate the role of hydrodynamic memory and its interplay with medium viscoelasticity for a free and a harmonically confined particle. The elastic response at high frequencies introduces oscillations in the VACF, which are found to be strongly damped by the coupling to the fluid. We show that in all Maxwell fluids hydrodynamic memory eventually leads to a power-law decay in the VACF as is already known for Newtonian fluids. The MSD displays asymptotically an intermediate plateau reflecting the elastic restoring forces of the medium. In the frequency domain, the PSD exhibits at high frequencies a step due to the trapping, whereas the low-frequency decay reflects the viscoelastic relaxation. Our results suggest that high-frequency microrheology is well-suited to infer the elastic modulus, which is sensitive over a wide range of Maxwell times.