Conventionally, nanograined metals and alloys can be stabilized through segregating foreign elements at grain boundaries (GBs). Yet such an effect may be offset by formation of second phase at elevated temperatures. In this paper, by introducing minor W into a binary Ni-Mo alloy, we found precipitation of intermetallic phases was suppressed, enhancing thermal stability of the nanograined structure. Characterized faceted GBs and a high-fraction of Σ3 coincidence site lattice (CSL) boundaries illustrate that GB structures are relaxed by formation of copious annealing twins. Adding W reduces stacking fault energy of the solid solution and facilitates the thermally-triggered GB relaxation. Suppressed precipitation of the intermetallic phases may be attributed to depletion of solutes at relaxed GBs.