The density and composition of a food matrix affect the rates of oral breakdown and in-mouth flavor release as well as the overall sensory experience. Agar gels of increasing concentration (1.0, 1.7, 2.9, and 5% agarose) with and without added fat (0, 2, 5, and 10%) were spiked with seven aroma volatiles. Differences in oral processing and sensory perception were systematically measured by a trained panel using a discrete interval time intensity method. Volatile release was measured in vivo and in vitro by proton transfer reaction mass spectrometry. Greater oral processing was required as agar gel strength increased, and the intensity of flavor-related sensory attributes decreased. Volatile release was inversely related to gel strength, showing that physicochemical phenomena were the main mechanisms underlying the perceived sensory changes. Fat addition reduced the amount of oral processing and had differential effects on release, depending on the fat solubility or lipophilicity of the volatiles.