We describe the goals, design, implementation, and initial progress of the UKIRT Infrared Deep Sky Survey (UKIDSS), a seven-year sky survey which began in 2005 May. UKIDSS is being carried out using the UKIRT Wide Field Camera (WFCAM), which has the largest étendue of any infrared astronomical instrument to date. It is a portfolio of five survey components covering various combinations of the filter set ZYJHK and H2. The Large Area Survey, the Galactic Clusters Survey, and the Galactic Plane Survey cover approximately 7000deg2 to a depth of K ~ 18; the Deep Extragalactic Survey covers 35deg2 to K ~ 21, and the Ultra Deep Survey covers 0.77deg2 to K ~ 23. Summed together UKIDSS is 12 times larger in effective volume than the 2MASS survey. The prime aim of UKIDSS is to provide a long-term astronomical legacy data base; the design is, however, driven by a series of specific goals - for example, to find the nearest and faintest substellar objects, to discover Population II brown dwarfs, if they exist, to determine the substellar mass function, to break the z = 7 quasar barrier; to determine the epoch of re-ionization, to measure the growth of structure from z = 3 to the present day, to determine the epoch of spheroid formation, and to map the Milky Way through the dust, to several kpc. The survey data are being uniformly processed. Images and catalogues are being made available through a fully queryable user interface - the WFCAM Science Archive (http://surveys.roe.ac.uk/wsa). The data are being released in stages. The data are immediately public to astronomers in all ESO member states, and available to the world after 18 months. Before the formal survey began, UKIRT and the UKIDSS consortia collaborated in obtaining and analysing a series of small science verification (SV) projects to complete the commissioning of the camera. We show some results from these SV projects in order to demonstrate the likely power of the eventual complete survey. Finally, using the data from the First Data Release, we assess how well UKIDSS is meeting its design targets so far.