A search for a heavy gauge boson W' has been conducted by the CMS experiment at the LHC in the decay channel with an electron and large transverse energy imbalance, using proton-proton collision data corresponding to an integrated luminosity of 36 inverse picobarns. No excess above standard model expectations is seen in the transverse mass distribution of the electron-(missing E_T) system. Assuming standard-model-like couplings and decay branching fractions, a W' boson with a mass less than 1.36 TeV/c^2 is excluded at 95% confidence level.