A three-dimensional memory device includes an alternating stack of insulating layers and electrically conductive layers located over a substrate and memory stack structures extending through the alternating stack. Each of the electrically conductive layers includes a stack of a compositionally graded diffusion barrier and a metal fill material portion, and the compositionally graded diffusion barrier includes a substantially amorphous region contacting the interface between the compositionally graded diffusion barrier and a substantially crystalline region that is spaced from the interface by the amorphous region. The substantially crystalline region effectively blocks atomic diffusion, and the amorphous region induces formation of large grains during deposition of the metal fill material portions.