State-of-the-art first-principle all-electron density functional theory calculations on small sodium clusters are performed to study the temperature dependency of their polarizabilities. For this purpose Born-Oppenheimer molecular dynamics simulations with more than 100 000 time steps (> 200 ps) are recorded employing gradient corrected functionals in combination with a double-zeta valence polarization basis set. For each cluster 18 trajectories between 50 and 900 K are collected. The cluster polarizabilities are then calculated along these trajectories employing a triple-zeta valence polarization basis set augmented with field-induced polarization functions. The analysis of these calculations shows that the temperature dependency of the sodium cluster polarizabilities varies strongly with cluster size. For several clusters characteristic changes in the polarizability per atom as a function of temperature are observed. It is shown that the inclusion of finite temperature effects resolves the long-standing mismatch between calculated and measured sodium cluster polarizabilities.