Heisenberg interactions are ubiquitous in magnetic materials and have been prevailing in modeling and designing quantum magnets. Bond-directional interactions offer a novel alternative to Heisenberg exchange and provide the building blocks of the Kitaev model, which has a quantum spin liquid (QSL) as its exact ground state. Honeycomb iridates, A2IrO3 (A=Na,Li), offer potential realizations of the Kitaev model, and their reported magnetic behaviors may be interpreted within the Kitaev framework. However, the extent of their relevance to the Kitaev model remains unclear, as evidence for bond-directional interactions remains indirect or conjectural. Here, we present direct evidence for dominant bond-directional interactions in antiferromagnetic Na2IrO3 and show that they lead to strong magnetic frustration. Diffuse magnetic x-ray scattering reveals broken spin-rotational symmetry even above Neel temperature, with the three spin components exhibiting nano-scale correlations along distinct crystallographic directions. This spin-space and real-space entanglement directly manifests the bond-directional interactions, provides the missing link to Kitaev physics in honeycomb iridates, and establishes a new design strategy toward frustrated magnetism.