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 co-variability, primarily at scales near the resolution of the ocean model grid. Enhancement in the SST-LHF anomaly covariance, and correlations, indicate that the ocean-intrinsic component of the air-sea heat flux variability improves with respect to high-resolution satellite observations, especially in Gulf Stream region.