We have synthesized nanoscale magnetic compasses with high yield. These ferromagnetic iron carbide nano-particles, which are encapsulated in a pair of parallel carbon needles, change their direction in response to an external magnetic field. Electron holography reveals magnetic fields confined to the vicinity of the bicone-shaped particles, which are composed of few ferromagnetic domains. Aligned magnetically and encapsulated in an acrylate polymer matrix, these nanocompasses exhibit anisotropic bulk magnetic permeability with an easy axis normal to the needle direction, that can be understood as a result of the anisotropic demagnetizing field of a nonspherical single-domain particle. This novel material with orthogonal magnetic and structural axes could be highly useful as magnetic components in electromagnetic wave absorbent materials and magnetorheological fluids.