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 May 2005, using the UKIRT Wide Field Camera. It is a portfolio of five survey components covering various combinations of the filter set ZYJHK and H_2. The Large Area Survey, the Galactic Clusters Survey, and the Galactic Plane Survey cover approximately 7000 square degrees to a depth of K~18; the Deep Extragalactic Survey covers 35 square degrees to K~21, and the Ultra Deep Survey covers 0.77 square degrees 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 database; the design is however driven by a series of specific goals -- for example to find the nearest and faintest sub-stellar 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-ionisation; 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, and released in stages through the WFCAM Science Archive (WSA : http://surveys.roe.ac.uk/wsa). Before the formal survey began, UKIRT and the UKIDSS consortium 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.