Aims: We report the discovery of very shallow (Δ F/F ≈ 3.4× 10-4), periodic dips in the light curve of an active V = 11.7 G9V star observed by the CoRoT satellite, which we interpret as caused by a transiting companion. We describe the 3-colour CoRoT data and complementary ground-based observations that support the planetary nature of the companion. Methods: We used CoRoT colours information, good angular resolution ground-based photometric observations in- and out- of transit, adaptive optics imaging, near-infrared spectroscopy, and preliminary results from radial velocity measurements, to test the diluted eclipsing binary scenarios. The parameters of the host star were derived from optical spectra, which were then combined with the CoRoT light curve to derive parameters of the companion. Results: We examined all conceivable cases of false positives carefully, and all the tests support the planetary hypothesis. Blends with separation >0.40´´or triple systems are almost excluded with a 8 × 10-4 risk left. We conclude that, inasmuch we have been exhaustive, we have discovered a planetary companion, named CoRoT-7b, for which we derive a period of 0.853 59 ± 3 × 10-5 day and a radius of Rp = 1.68 ± 0.09 R_Earth. Analysis of preliminary radial velocity data yields an upper limit of 21 M_Earth for the companion mass, supporting the finding. Conclusions: CoRoT-7b is very likely the first Super-Earth with a measured radius. This object illustrates what will probably become a common situation with missions such as Kepler, namely the need to establish the planetary origin of transits in the absence of a firm radial velocity detection and mass measurement. The composition of CoRoT-7b remains loosely constrained without a precise mass. A very high surface temperature on its irradiated face, ≈1800-2600 K at the substellar point, and a very low one, ≈50 K, on its dark face assuming no atmosphere, have been derived. The CoRoT space mission, launched on 27 December 2006, has been developed and is operated by CNES, with the contribution of Austria, Belgium, Brazil, ESA, Germany, and Spain. First CoRoT data are available to the public from the CoRoT archive: http://idoc-corot.ias.u-psud.fr. The complementary observations were obtained with MegaPrime/MegaCam, a joint project of CFHT and CEA/DAPNIA, at the Canada-France-Hawaii Telescope (CFHT) which is operated by NRC in Canada, INSU-CNRS in France, and the University of Hawaii; ESO Telescopes at the La Silla and Paranal Observatories under programme ID 081.C-0413(C), DDT 282.C-5015; the IAC80 telescope operated by the Instituto de Astrofísica de Tenerife at the Observatorio del Teide; the Isaac Newton Telescope (INT), operated on the island of La Palma by the Isaac Newton group in the Spanish Observatorio del Roque de Los Muchachos of the Instituto de Astrofisica de Canarias; and at the Anglo-Australian Telescope that have been funded by the Optical Infrared Coordination network (OPTICON), a major international collaboration supported by the Research Infrastructures Programme of the European Commissions Sixth Framework Programme; Radial-velocity observations were obtained with the SOPHIE spectrograph at the 1.93m telescope of Observatoire de Haute Provence, France.