We report polarized and unpolarized neutron scattering measurements of the magnetic order in single crystals of Na0.5CoO2. Our data indicate that below T_N=88 K the spins form a novel antiferromagnetic pattern within the CoO2 planes, consisting of alternating rows of ordered and non-ordered Co ions. The domains of magnetic order are closely coupled to the domains of Na ion order, consistent with such a two-fold symmetric spin arrangement. Magnetoresistance and anisotropic susceptibility measurements further support this model for the electronic ground state.