Context: The space telescope Gaia is dedicated mainly to performing high-precision astrometry, but also spectroscopy and epoch photometry which can be used to study various types of photometric variability. One such variability type is exoplanetary transits. The photometric data accumulated so far have finally matured enough to allow the detection of some exoplanets. Aims: In order to fully exploit the scientific potential of Gaia, we search its photometric data for the signatures of exoplanetary transits. Methods: The search relies on a version of the Box-Least-Square (BLS) method, applied to a set of stars prioritized by machine-learning classification methods. An independent photometric validation was obtained using the public full-frame images of TESS. In order to validate the first two candidates, radial-velocity follow-up observations were performed using the spectrograph PEPSI of the Large Binocular Telescope (LBT). Results: The radial-velocity measurements confirm that two of the candidates are indeed hot Jupiters. Thus, they are the first exoplanets detected by Gaia - Gaia-1b and Gaia-2b. Conclusions: Gaia-1b and Gaia-2b demonstrate that the approach presented in this paper is indeed effective. This approach will be used to assemble a set of additional exoplanet candidates, to be released in Gaia third data release, ensuring better fulfillment of the exoplanet detection potential of Gaia.