The present study investigates novelties brought into the classic Biot's theory of propagation of elastic waves in a fluid-saturated porous solid by inclusion of non-Newtonian effects that are important, for example, for hydrocarbons. Based on our previous results (Tsiklauri and Beresnev, 2001), we investigated the propagation of rotational and dilatational elastic waves by calculating their phase velocities and attenuation coefficients as a function of frequency. We found that the replacement of an ordinary Newtonian fluid by a Maxwell fluid in the fluid-saturated porous solid results in: (a) an overall increase of the phase velocities of both the rotational and dilatational waves. With the increase of frequency these quantities tend to a fixed, higher level, as compared to the Newtonian limiting case, which does not change with the decrease of the Deborah number a. (b) The overall decrease of the attenuation coefficients of both the rotational and dilatational waves. With the increase of frequency these quantities tend to a progressively lower level, as compared to the Newtonian limiting case, as a decreases. (c) Appearance of oscillations in all physical quantities in the deeply non-Newtonian regime.