The flow of a uniform Bose gas at speeds greater than the Landau critical velocity nu(c) does not necessarily destroy superfluidity, but rather needs only to lead to a decrease of the superfluid mass density rho(s). Analyzing a weakly interacting Bose gas with a finite-range interparticle interaction that leads to a Landau critical velocity at nonzero quasiparticle momentum, we explicitly construct the (nonuniform) condensate for fluid flow faster than nu(c) and calculate the accompanying decrease in rho s. We briefly comment on the relation of the physics to other problems in superfluids, e.g., solitons and vortices in Bose-Einstein condensates, and critical currents in superconductors.