(Abridged) Studying continuum emission from interstellar dust is essential to locating and characterizing the highest density regions in the interstellar medium. In particular, the early stages of massive star formation remain poorly understood. Our goal is to produce a large-scale, systematic database of massive pre- and proto-stellar clumps in the Galaxy, to understand how and under what conditions star formation takes place. A well characterized sample of star-forming sites will deliver an evolutionary sequence and a mass function of high-mass, star-forming clumps. This systematic survey at submm wavelengths also represents a preparatory work for Herschel and ALMA. The APEX telescope is ideally located to observe the inner Milky Way. The Large APEX Bolometer Camera (LABOCA) is a 295-element bolometer array observing at 870 microns, with a beam size of 19". Taking advantage of its large field of view (11.4') and excellent sensitivity, we started an unbiased survey of the Galactic Plane, with a noise level of 50-70 mJy/beam: the APEX Telescope Large Area Survey of the Galaxy (ATLASGAL). As a first step, we covered 95 sq. deg. These data reveal 6000 compact sources brighter than 0.25 Jy, as well as extended structures, many of them filamentary. About two thirds of the compact sources have no bright infrared counterpart, and some of them are likely to correspond to the precursors of (high-mass) proto-stars or proto-clusters. Other compact sources harbor hot cores, compact HII regions or young embedded clusters. Assuming a typical distance of 5 kpc, most sources are clumps smaller than 1 pc with masses from a few 10 to a few 100 M_sun. In this introductory paper, we show preliminary results from these ongoing observations, and discuss the perspectives of the survey.