First principle DFT calculations are used to study the thermodynamic and kinetic properties of Na-ion insertion in TiO2 hollandite, a potential anode for Na-ion batteries. The experimentally observed phase transformation from tetragonal TiO2 (I4/m) to monoclinic Na0.25TiO2 (I2/m) is confirmed. At high Na-ion concentrations the calculated formation energies predict a first-order phase transition toward the layered O′3-Na0.68TiO2 structure. Further sodiation initiates a solid solution reaction toward the layered O3-NaTiO2 phase, which was recently brought forward as a promising anode for Na-ion batteries. This transformation irreversibly transforms the one-dimensional hollandite tunnel structure into the layered structure and potentially brings forward an alternative route toward the preparation of the hard to prepare O3-NaTiO2 material. Energy barrier calculations reveal fast Na-ion diffusion at low concentrations and sluggish diffusion upon reaching the N0.25TiO2 phase, rationalizing why experimentally the Na0.5TiO2 phase is not achieved. Detailed analysis of the kinetic behavior in the hollandite structure via molecular dynamics simulations reveals the importance of correlated atomic motions and dynamic lattice deformations for the Na-ion diffusion. In addition, exceptional Na-ion kinetics were predicted for the layered O′3-Na0.75TiO2 phase through a dominating divacancy hopping mechanism.