Air-sea flux variability has contributions from both ocean and atmosphere at different spatio-temporal scales. Atmospheric synoptic scales and the air-sea turbulent heat flux that they drive are well represented in climate models, but ocean mesoscales and their associated variability are often not well resolved due to non-eddy-resolving spatial resolutions of current climate models. We deploy a physics-based stochastic subgrid-scale parameterization for ocean density, that reinforces the lateral density variations due to oceanic eddies, and examine its effect on air-sea heat flux variability in a comprehensive coupled climate model. The stochastic parameterization substantially modifies sea surface temperature (SST) and latent heat flux (LHF) variability and their correlations, primarily at scales near the resolution of the ocean model grid. Changes in the SST-LHF anomaly correlations indicate that the ocean-intrinsic component of the air-sea heat flux variability improves with respect to the satellite observational product, especially in western boundary current extensions.