A search for time-integrated CP violation in D0 → h-h+ (h = K, π) decays is presented using 0.62 fb-1 of data collected by LHCb in 2011. The flavor of the charm meson is determined by the charge of the slow pion in the D∗+ → D0π+ and D∗- → D¯0π- decay chains. The difference in CP asymmetry between D0 → K-K+ and D0 → π-π+, ΔA<inf>CP</inf> ≈ A<inf>CP</inf>(K-K+)-A<inf>CP</inf>(π-π+), is measured to be [-0.82 ± 0.21(stat) ± 0.11(syst)]%. This differs from the hypothesis of CP conservation by 3.5 standard deviations. © 2012 CERN, for the LHCb Collaboration. Published by the American Physical Society under the terms of the Creative Commons Attribution 3.0 License. Further distribution of this work must maintain attribution to the author(s) and the published articles title, journal citation, and DOI.