Heterogeneous materials, such as rock, have extreme nonlinear elastic behavior (the coefficient characteriziing cubic anharmonicity is orders of magnitude greater than that of homogeneous materials) and striking hysteretic behavior (the stress-strain equation of state has discrete memory). A model of these materials, taking their macroscopic elastic properties to result from many mesoscopic hysteretic elastic units, is developed. The Preisach-Mayergoyz description of hysteretic systems and effective medium theory are combined to find the quasistatic stress-strain equation of state, the quasistatic modulus-stress relationship, and the dynamic modulus-stress relationship. Hysteresis with discrete memory is inherent in all three relationships. The dynamic modulus-stress relationship is characterized and used as input to the equation of motion for nonlinear elastic wave propagation. This equation of motion is examined for one-dimensional propagation using a Green function method. The out-of-phase component of the dynamic modulus due to hysteriesis is found to be responsible for the generation of odd harmonics and to determine the amplitude of the nonlinear attenuation. ¿ American Geophysical Union 1994