Na2IrO3, a honeycomb 5d5 oxide, has been recently identified as a potential realization of the Kitaev spin lattice. The basic feature of this spin model is that for each of the three metal-metal links emerging out of a metal site, the Kitaev interaction connects only spin components perpendicular to the plaquette defined by the magnetic ions and two bridging ligands. The fact that reciprocally orthogonal spin components are coupled along the three different links leads to strong frustration effects and nontrivial physics. While the experiments indicate zigzag antiferromagnetic order in Na2IrO3, the signs and relative strengths of the Kitaev and Heisenberg interactions are still under debate. Herein we report results of ab initio many-body electronic-structure calculations and establish that the nearest-neighbor exchange is strongly anisotropic with a dominant ferromagnetic Kitaev part, whereas the Heisenberg contribution is significantly weaker and antiferromagnetic. The calculations further reveal a strong sensitivity to tiny structural details such as the bond angles. In addition to the large spin-orbit interactions, this strong dependence on distortions of the Ir2O2 plaquettes singles out the honeycomb 5d5 oxides as a new playground for the realization of unconventional magnetic ground states and excitations in extended systems.