The development of new electrochromic materials and devices, like smart windows, has an enormous impact on the energy efficiency of modern society. One of the crucial materials in this technology is nickel oxide. Ni-deficient NiO shows anodic electrochromism, whose mechanism is still under debate. We use DFT+U calculations to show that Ni vacancy generation results in the formation of hole polarons localized at the two oxygens next to the vacancy. In the case of NiO bulk, upon Li insertion or injection of an extra electron into Ni-deficient NiO, one hole gets filled, and the hole bipolaron is converted into a hole polaron well-localized at one O atom, resulting from the transition between oxidized (colored) to reduced (bleached) state. In the case of the Ni-deficient NiO(001) surface, the qualitatively same picture is obtained upon embedding Li, Na, and K into the Ni surface vacancy, reinforcing the conclusion that the electron injection, resulting in the filling of the hole states, is responsible for the modulation of the optical properties of NiO. Hence, our results suggest a new mechanism of Ni-deficient NiO electrochromism not related to the change of the Ni oxidation states, i.e., the Ni2+/Ni3+ transition, but based on the formation and annihilation of hole polarons in oxygen p-states.