In a classical ideal plasma, a magnetic field is known to reduce the heat conductivity perpendicular to the field whereas it does not alter the one along the field. Here we show that, in strongly correlated plasmas that are observed at high pressure or/and low temperature, a magnetic field reduces the perpendicular heat transport much less and even {\it enhances} the parallel transport. These surprising observations are explained by the competition of kinetic, potential and collisional contributions to the heat conductivity. Our results are based on first principle molecular dynamics simulations of a one-component plasma.