The existence and stability of non-Abelian half-quantum vortices (HQVs) are established in ${}^{3}P_{2}$ superfluids in neutron stars with strong magnetic fields, the largest topological quantum matter in our Universe. Using a self-consistent microscopic framework, we find that one integer vortex is energetically destabilized into a pair of two non-Abelian HQVs due to the strong spin-orbit coupled gap functions. We find a topologically protected Majorana fermion on each HQV, thereby providing two-fold non-Abelian anyons characterized by both Majorana fermions and a non-Abelian first homotopy group.