Heavy oils have high densities and extremely high viscosities, and they exhibit viscoelastic behavior. Traditional rock physics based on Gassmann theory does not apply to materials saturated with viscoelastic fluids. We use an effective-medium approach known as coherent potential approximation (CPA) as an alternative fluid-substitution scheme for rocks saturated with viscoelastic fluids. Such rocks are modeled as solids with elliptical fluid inclusions when fluid concentration is small and as suspensions of solid particles in the fluid when the solid concentration is small. This approach is consistent with concepts of percolation and critical porosity, and it allows one to model sandstones and unconsolidated sands. We model the viscoelastic properties of a heavy-oil-saturated rock sample using CPA and a measured frequency-dependent complex shear modulus of the heavy oil. Comparison of modeled results with measured properties of the heavy-oil rock reveals a large discrepancy over a range of frequencies and temperatures. We modify the CPA scheme to account for the effect of binary pore structure by introducing a compliant porosity term. This dramatically improves the predictions. The predicted values of the effective shear modulus of the rock are in good agreement with laboratory data for the range of frequencies and temperatures. This confirms that our scheme realistically estimates the frequency- and temperature-dependent properties of heavy-oil rocks and can be used as an approximate fluid-substitution approach for rocks saturated with viscoelastic fluids.