We consider a two-fluid shear flow where the interface between the two fluids is coated with an insoluble surfactant. An asymptotic model is derived in the thin-layer approximation, consisting of a set of nonlinear partial differential equations describing the evolution of the film and surfactant disturbances at the interface. The model includes important physical effects such as Marangoni forces (caused by the presence of surfactant), inertial forces arising in the thick fluid layer, as well as gravitational forces. The aim of this study is to investigate the effect of density stratification or gravity—represented through the Bond number Bo—on the flow stability and the interplay between the different (de)stabilisation mechanisms. It is found that gravity can either stabilise or destabilise the interface (depending on fluid properties) but not always as intuitively anticipated. Different traveling-wave branches are presented for varying Bo, and the destabilising mechanism associated with the Marangoni forces is discussed.