The effect of stress on Lamb wave propagation is relevant to both nondestructive evaluation and structural health monitoring because of changes in received signals due to both the associated strain and the acoustoelastic effect. A homogeneous plate that is initially isotropic becomes anisotropic under biaxial stress, and dispersion of propagating waves becomes directionally dependent. The problem is similar to Lamb wave propagation in an anisotropic plate, except the fourth order tensor in the resulting wave equation does not have the same symmetry as that for the unstressed anisotropic plate, and the constitutive equation relating incremental stress to incremental strain is more complicated. Here we review the theory of acoustoelastic and develop theory for acoustoelastic Lamb wave propagation and show how dispersion curves shift anisotropically for an aluminum plate under biaxial tension. We also develop an approximate method using the effective elastic constants (EECs) and show that existing commercial tools to generate dispersion curves can be used under restricted conditions to describe wave propagation in biaxially stressed plates. Predictions of changes in phase velocity as a function of propagation direction using theory and the EEC method are compared to experimental results for a single wave mode.