We present a measurement of the time-dependent CP-violating asymmetry in B_s -> J/psi phi decays, using data collected with the LHCb detector at the LHC. The decay time distribution of B_s -> J/psi phi is characterized by the decay widths Gamma_H and Gamma_L of the heavy and light mass eigenstates of the B_s-B_s-bar system and by a CP-violating phase phi_s. In a sample of about 8500 B_s -> J/psi phi events isolated from 0.37 fb^-1 of pp collisions at sqrt(s)=7 TeV we measure phi_s = 0.15 +/- 0.18 (stat) +/- 0.06 (syst) rad. We also find an average B_s decay width Gamma_s == (Gamma_L + Gamma_H)/2 = 0.657 +/- 0.009 (stat) +/- 0.008 (syst) ps^-1 and a decay width difference Delta Gamma_s == Gamma_L - Gamma_H} = 0.123 +/- 0.029 (stat) +/- 0.011 (syst) ps^-1. Our measurement is insensitive to the transformation (phi_s,DeltaGamma_s -> pi - phi_s, - Delta Gamma_s.