While the selection of strongly lensed galaxies (SLGs) with 500 μm flux density S 500 > 100 mJy has proven to be rather straightforward, for many applications it is important to analyze samples larger than the ones obtained when confining ourselves to such a bright limit. Moreover, only by probing to fainter flux densities is it possible to exploit strong lensing to investigate the bulk of the high-z star-forming galaxy population. We describe HALOS (the Herschel-ATLAS Lensed Objects Selection), a method for efficiently selecting fainter candidate SLGs, reaching a surface density of ~= 1.5-2 deg-2, i.e., a factor of about 4-6 higher than that at the 100 mJy flux limit. HALOS will allow the selection of up to ~1000 candidate SLGs (with amplifications μ >~ 2) over the full H-ATLAS survey area. Applying HALOS to the H-ATLAS Science Demonstration Phase field (sime 14.4 deg2) we find 31 candidate SLGs, whose candidate lenses are identified in the VIKING near-infrared catalog. Using the available information on candidate sources and candidate lenses we tentatively estimate a ~= 72% purity of the sample. As expected, the purity decreases with decreasing flux density of the sources and with increasing angular separation between candidate sources and lenses. The redshift distribution of the candidate lensed sources is close to that reported for most previous surveys for lensed galaxies, while that of candidate lenses extends to redshifts substantially higher than found in the other surveys. The counts of candidate SLGs are also in good agreement with model predictions. Even though a key ingredient of the method is the deep near-infrared VIKING photometry, we show that H-ATLAS data alone allow the selection of a similarly deep sample of candidate SLGs with an efficiency close to 50%; a slightly lower surface density (sime 1.45 deg-2) can be reached with a ~70% efficiency. Herschel is an ESA space observatory with science instruments provided by European-led Principal Investigator consortia and with important participation from NASA.