We present a method to identify Ultra Faint Dwarf Galaxy (UFDG) candidates in the halo of the Milky Way using the future Gaia catalogue and we explore its detection limits and completeness. The method is based on the Wavelet Transform and searches for over-densities in the combined space of sky coordinates and proper motions, using kinematics in the search for the first time. We test the method with a Gaia mock catalogue that has the Gaia Universe Model Snapshot (GUMS) as a background, and use a library of around 30 000 UFDGs simulated as Plummer spheres with a single stellar population. For the UFDGs we use a wide range of structural and orbital parameters that go beyond the range spanned by real systems, where some UFDGs may remain undetected. We characterize the detection limits as function of the number of observable stars by Gaia in the UFDGs with respect to that of the background and their apparent sizes in the sky and proper motion planes. We find that the addition of proper motions in the search improves considerably the detections compared to a photometric survey at the same magnitude limit. Our experiments suggest that Gaia will be able to detect UFDGs that are similar to some of the known UFDGs even if the limit of Gaia is around 2 magnitudes brighter than that of SDSS, with the advantage of having a full-sky catalogue. We also see that Gaia could even find some UFDGs that have lower surface brightness than the SDSS limit.