The effects of grain size on magnetic and mechanical properties of Dy-free Nd-Fe-B sintered magnets were studied. The grain size of the sintered magnets was varied by using different sized Dy-free Nd-Fe-B alloy feedstock powders which were ball milled to different extents. Increasing the ball milling time from 7 to 11 h caused the average particle size of the powders to decrease from 3.6 to 2.1 µm, while the average grain size of the corresponding sintered magnets decreased from 5.0 to 4.0 µm. The intrinsic coercivity Hcj and maximum energy product (BH)max of these magnets increased from 11.6 to 13.7 kOe and 41.6 to 43.6 MGOe, respectively. The finer grain magnets exhibited better thermal stability, as indicated by a smaller temperature coefficient of Hcj (−0.71%/°C). With extending ball milling time to 15 h, the magnetic properties of the magnets deteriorate, while the flexural strengths first decrease and then increase. The flexural strength improvement is attributed to the increased Oxygen content in the magnets due to finer grains. The coercivity enhancement by reduction of grain size is a promising approach to develop Dy-free Nd-Fe-B sintered magnets with better thermal stability. It is important to control the Oxygen contents in the magnets to compromise both magnetic and mechanical properties.