Barium hexaferrite (BaFe12O19) magnetic powder was synthesized via ceramic route by mixing of Fe2O3 and BaCO3 and subsequent calcination of the mixed powder in air at 1150°C. The synthesized barium hexaferrite was mixed with graphite to be treated mechano-chemically in high energy ball mill in air atmosphere for various times. Subsequently, the milled samples were subjected to high temperature in argon atmosphere. XRD patterns of the milled samples revealed that graphite partially reduced barium hexaferrite to Fe3O4 after 15 hours of milling, resulted in a magnetic nano-composite of BaFe12O19/Fe3O4. Extending milling time to 80 hours promoted the reduction process to FeO. Heat treatment of the milled samples resulted in different magnetic composites. Iron was seen in XRD pattern of the 40 hours milled sample that was heat treated at 680°C. SEM images showed that after heat treatment, fine particles in agglomerates grew and larger particles formed. As a result, mean particle size increased due to the heat treatment of the milled powder.