ZrO2 nanoparticle dispersions containing associative polymers exhibit two relaxation modes: Maxwellian behavior at high frequency imparted by the associating polymers and a power law spectrum at low frequency generated by the particle dynamics. The timescales and volume fraction dependence of the dispersions reflect weak attractions between particles with adsorbed polymer layers dispersed in a percolated network of associative polymer. The Baxter stickiness parameter extracted from the high frequency viscosity data indicates strong attractions, whereas the high frequency modulus reveals three sources of elasticity: micelle-micelle associations in the solution, rigidity of the particles and adsorbed layer, and adsorbed layer-adsorbed layer interactions. The sol-gel transition of the dispersions occurs around 12-14% particle loading. Comparison with latex dispersions suggests a slower relaxation mode and greater rigidity with the ZrO2 particles.