The impact of non-Newtonian drops (equilibrium diameter: similar to 3 mm) on a heated surface in the Leidenfrost regime is studied experimentally by high-speed imaging. Impact Weber numbers in the range of 10 and 200 have been compared with the impact of water drops for the same conditions. Dilute solutions of polyethylene oxide in de-ionized water were used as model viscoelastic fluids, with a polymer mass concentration of 300 ppm; a xanthan gum solution was used as a model shear-thinning fluid (300 ppm weight concentration). Results show that polymer additives change the scaling of the maximum spreading diameter with respect to the Weber number, and increase the maximum bouncing height of drops. This suggests a different distribution of the initial impact kinetic energy with respect to drops of pure water.