We compute the gluon polarization tensor in a thermo-magnetic environment in the strong magnetic field limit at zero and high temperature. The magnetic field effects are introduced using Schwinger's proper time method. Thermal effects are computed in the HTL approximation. At zero temperature, we reproduce the well-known result whereby for a non-vanishing quark mass, the polarization tensor reduces to the parallel structure and its coefficient develops an imaginary part corresponding to the threshold for quark-antiquark pair production. This coefficient is infrared finite and simplifies considerably when the quark mass vanishes. Keeping always the field strength as the largest energy scale, in the high temperature regime we analyze two complementary hierarchies of scales: q(2) << m(f)(2) << T-2 and m(f)(2) << q(2) << T-2. In the latter, we show that the polarization tensor is infrared finite as m(f) goes to zero. In the former, we discuss the thermal corrections to the magnetic Debye mass.