We report a combined experimental and theoretical investigation of the magnetic structure of the honeycomb lattice magnet Na$_2$IrO$_3$, a strong candidate for a realization of a gapless spin-liquid. Using resonant x-ray magnetic scattering at the Ir L$_3$-edge, we find 3D long range antiferromagnetic order below T$_N$=13.3 K. From the azimuthal dependence of the magnetic Bragg peak, the ordered moment is determined to be predominantly along the {it a}-axis. Combining the experimental data with first principles calculations, we propose that the most likely spin structure is a novel zig-zag structure.