This Letter describes the search for a new heavy charged gauge boson W' decaying into an electron and a neutrino. The data were collected with the D0 detector at the Fermilab Tevatron proton-antiproton Collider at a center-of-mass energy of 1.96 TeV, and correspond to an integrated luminosity of about 1 inverse femtobarn. Lacking any significant excess in the data in comparison with known processes, an upper limit is set on the production cross section times branching fraction, and a W' boson with mass below 1.00 TeV can be excluded at the 95% C.L., assuming standard-model-like couplings to fermions. This result significantly improves upon previous limits, and is the most stringent to date.