In this work, nano-composite of barium hexaferrite/magnetite was produced by partial reduction of barium hexaferrite with graphite via ball milling. Phase composition, morphology and magnetic properties of the samples were evaluated by XRD, SEM and VSM, respectively. XRD results revealed that after 15 hours milling, a nano-composite of BaFe12O19/Fe3O4 formed which mean crystallite size of BaFe12O19 was 17 nm. After milling for 20 and 40 hours, the peaks of BaFe12O19 were weakened and Fe3O4 was detected as a dominant phase. The coercivity decreased from 703 to 153 Oe when the milling time increased from 15 to 20 hours.