For thermal mixed-convection flows, the Nusselt number is a function of Reynolds number, Grashof number and the angle between the forced-and natural-convection directions. We consider flow over a heated cylinder for which there is no universal correlation that accurately predicts Nusselt number as a function of these parameters, especially in opposing-convection flows, where the natural convection is against the forced convection. Here, we revisit this classical problem by employing modern tools from machine learning to develop a general multi-fidelity framework for constructing a stochastic response surface for the Nusselt number. In particular, we combine previously developed experimental correlations (low-fidelity model) with direct numerical simulations (high-fidelity model) using Gaussian process regression and autoregressive stochastic schemes. In this framework the high-fidelity model is sampled only a few times, while the inexpensive empirical correlation is sampled at a very high rate. We obtain the mean Nusselt number directly from the stochastic multi-fidelity response surface, and we also propose an improved correlation. This new correlation seems to be consistent with the physics of this problem as we correct the vectorial addition of forced and natural convection with a pre-factor that weighs differently the forced convection. This, in turn, results in a new definition of the effective Reynolds number, hence accounting for the 'incomplete similarity' between mixed convection and forced convection. In addition, due to the probabilistic construction, we can quantify the uncertainty associated with the predictions. This information-fusion framework is useful for elucidating the physics of the flow, especially in cases where anomalous transport or interesting dynamics may be revealed by contrasting the variable fidelity across the models. While in this paper we focus on the thermal mixed convection, the multi-fidelity framework provides a new paradigm that could he used in many different contexts in fluid mechanics including heat and mass transport, but also in combining various levels of fidelity of models of turbulent flows.