Thermodynamics is one of the most successful physical theories ever formulated. Though it was initially developed to deal with steam engines and, in particular, the problem of conversion of heat into mechanical work, it has prevailed even after the scientific revolutions of relativity and quantum mechanics. Despite its wide range of applicability, it is known that the laws of thermodynamics break down when systems are correlated with their environments. In the presence of correlations, anomalous heat flows from cold to hot baths become possible, as well as memory erasure accompanied by work extraction instead of heat dissipation. Here, we generalize thermodynamics to physical scenarios which allow the presence of correlations, including those where strong correlations are present. We exploit the connection between information and physics, and introduce a consistent redefinition of heat dissipation by systematically accounting for the information flow from system to bath in terms of the conditional entropy. As a consequence, the formula for the Helmholtz free energy is accordingly modified. Such a remedy not only fixes the apparent violations of Landauer’s erasure principle and the second law due to anomalous heat flows, but it also leads to a reformulation of the laws of thermodynamics that are universally respected. In this information-theoretic approach, correlations between system and environment store work potential. Thus, in this view, the apparent anomalous heat flows are the refrigeration processes driven by such potentials.