We present a search for the production of a new heavy gauge boson W' that decays to a top quark and a bottom quark. We have analyzed 230 pb−1 of data collected with the D0 detector at the Fermilab Tevatron collider at a center-of-mass energy of 1.96 TeV. No significant excess of events is found in any region of the final state invariant mass distribution. We set upper limits on the production cross section of W bosons at the 95% confidence level for several different W' boson masses. We exclude masses below 610 GeV for a W' boson with standard-model-like couplings, below 630 GeV for a W' boson with right-handed couplings that is allowed to decay to both leptons and quarks, and below 670 GeV for a W' boson with right-handed couplings that is only allowed to decay to quarks.