A theoretical study is made on the nuclear spin relaxation in magnetic crystals near their Curie temperatures. The exchange narrowed hyperfine broadening of the NMR line width is shown to increase due to the slowing down of a certain part of the electron spin fluctuations as the transition point is approached, giving rise to the line width whose asymptotic value near the transition point is proportional to [TC / (T-TC)]3/2 in cubic ferromagnets and to [TN / (T-TN)]1/2 in cubic antiferromagnets. The spin-lattice relaxation rate is dominated by this mechanism and has the same value as the above contribution to the line width. The effect of the anisotropy and the external magnetic field on this mechanism is also discussed. The indirect nuclear spin interaction via the hyperfine interaction is treated from a general point of view by using the wavelength dependent susceptibility. The susceptibility is calculated with the use of a molecular field approximation. Since the spatial correlation between the spins becomes long ranged as the transition point is approached, the indirect nuclear spin interaction becomes long ranged at the same time. In non-cubic crystals this interaction gives rise to the line width whose asymptotic value near the transition point (both above and below TC) is proportional to [TC / |T-TC|]1/4 both in ferro- and antiferromagnets and the coefficient of this temperature factor is of the same order of magnitude as those in the first mechanism. In cubic crystals this effect vanishes or is reduced by orders of magnitude. The theory is compared with the F19-resonance experiments in MnF2 and the agreement is not unreasonable.