The relationship between mechanical properties and microstructures in sintered WC-FeAl composite was investigated in this work. Milling time was used as the linking parameter of the mechanical properties and the microstructure. The change of milling time led to various microstructures consisting of WC and FeAl phases. Sizes of FeAl phases became smaller with increasing the milling time while WC grain sizes were not changed. Vickers hardness was improved with increasing the milling whereas indentation fracture toughness and transverse rupture strength kept almost constant. This size reduction of FeAl phases increased the hardness but did not influence the fracture toughness and strength unless there was no huge FeAl pool. It was concluded that the sizes of FeAl phases were very important for improving the hardness of a sintered WC-FeAl composite prepared from wet milling process.