We report the first detection of CO (1-->0) emission from a submillimeter-selected galaxy, using the Green Bank Telescope. We identify the line in the spectrum of SMM J13120+4242 as a broad emission feature at z=3.408, with DeltaVFWHM=1040+/-190 km s-1. If the observed CO (1-->0) line profile arises from a single object and not several merging objects, then the CO (4-->3)/CO (1-->0) brightness temperature ratio of ~0.26 suggests n(H2)>(3-10)×102 cm-3 and the presence of subthermally excited gas. The integrated line flux implies a cold molecular gas mass M(H2)=1.6×1011 Msolar, comparable to the dynamical mass estimate and 4 times larger than the H2 mass predicted from the CO (4-->3) line, assuming a brightness temperature ratio of 1.0. While our observations confirm that this submillimeter galaxy is massive and gas-rich, they also suggest that extrapolating gas masses from Jupper>=3 transitions of CO leads to considerable uncertainties. We also report an upper limit to the mass of cold molecular gas in a second submillimeter galaxy, SMM J09431+4700, of M(H2)