We present the first measurement of the production cross section of a W boson with a single charm quark (c) in pp collisions at sqrt(s)=1.96 TeV, using soft muon tagging of c jets. In a data sample of approximately 1.8 fb(-1), recorded with the Collider Detector at Fermilab II detector at the Fermilab Tevatron, we select events with W+1 or 2 jets. We use the charge correlation between the W and the muon from the semileptonic decay of a charm hadron to extract the Wc signal. We measure sigma Wc(PTc >20 GeV/c,|eta c|<1.5) x BR(W-->l nu)=9.8+/-3.2 pb, in agreement with theoretical expectations.