The VSOP mission is a Japanese-led project to image radio sources with sub-milliarcsec resolution by correlating the signal from the orbiting 8-m telescope, HALCA, with a global array of telescopes. Twenty- five percent of the scientific time of this mission is devoted to a survey of 402 bright, small-diameter extra-galactic radio sources at 5-GHz. The major goals of the VSOP Survey are statistical in nature: to determine the brightness temperature and approximate structure; to provide a source list for use with future space VLBI missions; and to compare radio properties with other data throughout the EM spectrum. This paper describes: the compilation of a complete list of radio sources associated with active galactic nuclei (AGN); the selection of the subsample of sources to be observed with VSOP; the extensive ground resources used for the Survey; the status of the observations as of 2000 July; the data-analysis methods; and several examples of results from the VSOP Survey. More detailed results from the full sample will be given in future papers.