We present source catalogs for the 4 Ms Chandra Deep Field-South (CDF-S), which is the deepest Chandra survey to date and covers an area of 464.5 arcmin2. We provide a main Chandra source catalog, which contains 740 X-ray sources that are detected with WAVDETECT at a false-positive probability threshold of 10--5 in at least one of three X-ray bands (0.5-8 keV, full band; 0.5-2 keV, soft band; and 2-8 keV, hard band) and also satisfy a binomial-probability source-selection criterion of P < 0.004 (i.e., the probability of sources not being real is less than 0.004); this approach is designed to maximize the number of reliable sources detected. A total of 300 main-catalog sources are new compared to the previous 2 Ms CDF-S main-catalog sources. We determine X-ray source positions using centroid and matched-filter techniques and obtain a median positional uncertainty of 042. We also provide a supplementary catalog, which consists of 36 sources that are detected with WAVDETECT at a false-positive probability threshold of 10--5, satisfy the condition of 0.004 < P < 0.1, and have an optical counterpart with R < 24. Multiwavelength identifications, basic optical/infrared/radio photometry, and spectroscopic/photometric redshifts are provided for the X-ray sources in the main and supplementary catalogs. Seven hundred sixteen (97%) of the 740 main-catalog sources have multiwavelength counterparts, with 673 (94% of 716) having either spectroscopic or photometric redshifts. The 740 main-catalog sources span broad ranges of full-band flux and 0.5-8 keV luminosity; the 300 new main-catalog sources span similar ranges although they tend to be systematically lower. Basic analyses of the X-ray and multiwavelength properties of the sources indicate that >75% of the main-catalog sources are active galactic nuclei (AGNs); of the 300 new main-catalog sources, about 35% are likely normal and starburst galaxies, reflecting the rise of normal and starburst galaxies at the very faint flux levels uniquely accessible to the 4 Ms CDF-S. Near the center of the 4 Ms CDF-S (i.e., within an off-axis angle of 3'), the observed AGN and galaxy source densities have reached 9800+1300 -- 1100 deg--2 and 6900+1100 -- 900 deg--2, respectively. Simulations show that our main catalog is highly reliable and is reasonably complete. The mean backgrounds (corrected for vignetting and exposure-time variations) are 0.063 and 0.178 counts Ms--1 pixel--1 (for a pixel size of 0492) for the soft and hard bands, respectively; the majority of the pixels have zero background counts. The 4 Ms CDF-S reaches on-axis flux limits of 3.2 X 10--17, 9.1 X 10--18, and 5.5 X 10--17 erg cm--2 s--1 for the full, soft, and hard bands, respectively. An increase in the CDF-S exposure time by a factor of 2-2.5 would provide further significant gains and probe key unexplored discovery space.