This study investigates the effect of substituting sunflower oil with two starch-based fat-replacers on the rheological and lubricating properties, as well as the sensory properties of reduced-fat mayonnaise-type emulsions. Lipid-modified maize starch fat replacers containing amylose–lipid complexes, maize starch with 1.5% stearic acid and maize starch with 2% monoglyceride, are used to formulate reduced-fat mayonnaise-type emulsions at 0% (full-fat control), 50%, 80%, and 98% level of oil replacement. Reduced-fat emulsions containing starch/monoglyceride are rated similar (p > 0.05) to the full-fat mayonnaise at all the oil replacement levels in terms of smoothness, creaminess, melting, and mouth-coating. They also have similarities in terms of thickness and easy-to-swallow sensory attributes, up to a 50% substitution level. For the corresponding starch/stearic acid emulsions, the smoothness, thickness, creaminess, and mouth-coating attributes are rated lower while the melting and easy-to-swallow attributes are rated higher than for the starch/monoglyceride emulsions. In general, all the reduced-fat emulsions exhibit good lubrication. The ability of the reduced-fat emulsions to support the highly viscous structure provided by the presence of amylose–lipid complexes in the fat replacers is better for the starch/monoglyceride fat replacer than for the starch/stearic acid fat replacer.