The challenge of producing dense ultrafine-grained (UFG) tungsten is hereby addressed by a simple pressureless two-step sintering method. It provides a uniform microstructure with ~99% theoretical density and ~700 nm grain size, which is among the best sintering practice of pure tungsten reported in the literature. Benefitting from the finer and more uniform microstructures, two-step sintered samples show better mechanical properties in bending strength and hardness. While parabolic grain growth kinetics is verified, a transition in the nominal grain boundary mobility was observed at 1400 °C, above which the effective activation enthalpy is ~6.1 eV, below which grain boundary motion is rapidly frozen with unusually large activation enthalpy of ~12.9 eV. Such highly nonlinear behavior in activation parameters with respect to temperature suggests that activation entropy and maybe collective behavior play a role in grain growth. We believe the as-reported two-step sintering method should also be applicable to other refractory metals and alloys, and may be generalized to multi-step or continuous-cooling sintering design using machine learning.