Classical lubrication theory is unable to explain a variety of phenomena and experimental observations involving soft viscoelastic materials, which are ubiquitous and increasingly used in e.g. engineering and biomedical applications. These include unexpected ruptures of the lubricating film and a friction-speed dependence, which cannot be elucidated by means of conventional models, based on time-independent stress-strain constitutive laws for the lubricated solids. A new modeling framework, corroborated through experimental measurements enabled via an interferometric technique, is proposed to address these issues: Solid/fluid interactions are captured thanks to a coupling strategy that makes it possible to study the effect that solid viscoelasticity has on fluid film lubrication. It is shown that a newly defined visco-elasto-hydrodynamic lubrication (VEHL) regime can be experienced depending on the degree of coupling between the fluid flow and the solid hysteretic response. Pressure distributions show a marked asymmetry with a peak at the flow inlet, and correspondingly, the film thickness reveals a pronounced shrinkage at the flow outlet; friction is heavily influenced by the viscoelastic hysteresis which is experienced in addition to the viscous losses. These features show significant differences with respect to the classical elasto-hydrodynamic lubrication (EHL) regime response that would be predicted when solid viscoelasticity is neglected. A simple yet powerful criterion to assess the importance of viscoelastic solid contributions to soft matter lubrication is finally proposed.