The D0 Collaboration presents first evidence for the production of single top quarks at the Fermilab Tevatron p collider. Using a 0.9 fb-1 dataset, we apply a multivariate analysis to separate signal from background and measure (ptb+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.