The effect of grain size and temperature on the mechanical behavior of nano-polycrystal magnesium under tensile load is investigated using molecular dynamics simulation. The results indicate that the average flow stress of nano-polycrystal magnesium decreases with decreasing grain size, exhibiting a breakdown in the Hall-Petch relation when grain size is smaller than a critical size. The results also show that crack formation during tension is a cause of reduced flow stress of nano-polycrystal magnesium with a large grain size and that the Young’s modulus of nano-polycrystal magnesium increases with increasing grain size. Furthermore, we find that the deformation behavior of nano-polycrystal magnesium obviously depends on temperatures.