To clarify the microstructure and fracture characteristics of heat-affected zone in shipbuilding steel plates with Mg deoxidation after high heat input welding, two steels with 0.0002 (2Mg) and 0.0049 (49Mg) wt% Mg are prepared and investigated with metallography and crystallography. Compared with 2Mg, TiN particles are incrementally refined in 49Mg, making the prior austenite grain (PAG) size decrease. In the large-sized grains of 2Mg, there are preferentially formed coarse grain boundary ferrites (GBFs) and ferrite side plates (FSPs), followed by intragranular bainite ferrites (IBFs). The small PAGs of 49Mg make fine-grained polygonal ferrites (PFs) dominate the microstructure. With Mg addition, the effective grain with θ > 50° refines and the high-angle grain boundary density increases. The brittle transgranular fracture occurs around little-deformed coarse GBFs, FSPs, and IBFs with θ < 15° in 2Mg, showing the weak crack resistance. However, in 49Mg, the ductile fracture occurs around fine PFs and IAFs with large plastic deformation. Although there is transgranular fracture in coarse PFs, it can be soon deflected and arrested by small-sized PFs with θ > 50° in 49Mg. Thus, for 49Mg, the crack initiation and propagation energies increase with the toughness at −40 °C increasing from 20 to 167 J.