The effect of heterogeneous sequence composition on the denaturation of double stranded DNA is investigated. The resulting pair-binding energy variation is found to have a negligible effect on the critical properties of the smooth second order melting transition in the simplest (Peyrard-Bishop) model. However, sequence heterogeneity is dramatically amplified upon adopting a more realistic treatment of the backbone stiffness. The model yields features of ``multi-step melting'' similar to those observed in experiments.