The Spitzer Survey of Stellar Structure in Galaxies ( 4G ) is an Exploration Science Legacy Program approved for the Spitzer post-cryogenic mission. It is a volume-, magnitude-, and size-limited ( d < 40 Mpc , | b | > 30 ° , mBcorr < 15.5 , and D25 > 1') survey of 2331 galaxies using the Infrared Array Camera (IRAC) at 3.6 and 4.5 μm. Each galaxy is observed for 240 s and mapped to ≥ 1.5 × D25 . The final mosaicked images have a typical 1σ rms noise level of 0.0072 and 0.0093 MJy sr-1 at 3.6 and 4.5 μm, respectively. Our azimuthally averaged surface brightness profile typically traces isophotes at μ3.6 μm ( AB ) ( 1 σ ) ˜ 27 mag arcsec-2 , equivalent to a stellar mass surface density of ˜ 1 M&sun; pc-2. S4G thus provides an unprecedented data set for the study of the distribution of mass and stellar structures in the local universe. This large, unbiased, and extremely deep sample of all Hubble types from dwarfs to spirals to ellipticals will allow for detailed structural studies, not only as a function of stellar mass, but also as a function of the local environment. The data from this survey will serve as a vital testbed for cosmological simulations predicting the stellar mass properties of present-day galaxies. This article introduces the survey and describes the sample selection, the significance of the 3.6 and 4.5 μm bands for this study, and the data collection and survey strategies. We describe the S4G data analysis pipeline and present measurements for a first set of galaxies, observed in both the cryogenic and warm mission phases of Spitzer. For every galaxy we tabulate the galaxy diameter, position angle, axial ratio, inclination at μ3.6 μm ( AB ) = 25.5 , and 26.5 mag arcsec-2 (equivalent to ≈ μB ( AB ) = 27.2 and 28.2 mag arcsec-2 , respectively). These measurements will form the initial S4G catalog of galaxy properties. We also measure the total magnitude and the azimuthally averaged radial profiles of ellipticity, position angle, surface brightness, and color. Finally, using the galaxy-fitting code GALFIT, we deconstruct each galaxy into its main constituent stellar components: the bulge/spheroid, disk, bar, and nuclear point source, where necessary. Together, these data products will provide a comprehensive and definitive catalog of stellar structures, mass, and properties of galaxies in the nearby universe and will enable a variety of scientific investigations, some of which are highlighted in this introductory S4G survey paper.