The D0 Collaboration presents first evidence for the production of single top quarks at the Fermilab Tevatron pp¯ collider. Using a 0.9 fb−1 dataset, we apply a multivariate analysis to separate signal from background and measure σ(pp¯→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 a signal is 0.035%, corresponding to a 3.4 standard deviation significance. We use the cross section measurement to directly determine the Cabibbo-Kobayashi-Maskawa matrix element that describes the Wtb coupling and find 0.68<|Vtb|≤1 at 95% C.L. within the standard model.Received 22 December 2006DOI:https://doi.org/10.1103/PhysRevLett.98.181802©2007 American Physical Society