The D0 Collaboration presents first evidence for the production of single top quarks at the Fermilab Tevatron ppbar collider. Using a 0.9 fb^-1 dataset, we apply a multivariate analysis to separate signal from background and measure sigma(ppbar->tb+X,tqb+X) = 4.9 +- 1.4 pb. The probability to measure a cross section at this value or higher in the absence of signal is 0.035%, corresponding to a 3.4 standard deviation significance. We use the cross section measurement to directly determine the CKM matrix element that describes the Wtb coupling and find 0.68 < |Vtb| <= 1 at 95% C.L. within the standard model