We present the C4 Cluster Catalog, a new sample of 748 clusters of galaxies identified in the spectroscopic sample of the Second Data Release (DR2) of the Sloan Digital Sky Survey (SDSS). The C4 cluster-finding algorithm identifies clusters as overdensities in a seven-dimensional position and color space, thus minimizing projection effects that have plagued previous optical cluster selection. The present C4 catalog covers ~2600 deg2 of sky and ranges in redshift from z = 0.02 to 0.17. The mean cluster membership is 36 galaxies (with measured redshifts) brighter than r = 17.7, but the catalog includes a range of systems, from groups containing 10 members to massive clusters with over 200 cluster members with measured redshifts. The catalog provides a large number of measured cluster properties including sky location, mean redshift, galaxy membership, summed r-band optical luminosity (Lr), and velocity dispersion, as well as quantitative measures of substructure and the surrounding large-scale environment. We use new, multicolor mock SDSS galaxy catalogs, empirically constructed from the ΛCDM Hubble Volume (HV) Sky Survey output, to investigate the sensitivity of the C4 catalog to the various algorithm parameters (detection threshold, choice of passbands, and search aperture), as well as to quantify the purity and completeness of the C4 cluster catalog. These mock catalogs indicate that the C4 catalog is ∼–90% complete and 95% pure above M200 = 1 × 1014 h-1 M⊙ and within 0.03 ≤ z ≤ 0.12. Using the SDSS DR2 data, we show that the C4 algorithm finds 98% of X-ray–identified clusters and 90% of Abell clusters within 0.03 ≤ z ≤ 0.12. Using the mock galaxy catalogs and the full HV dark matter simulations, we show that the Lr of a cluster is a more robust estimator of the halo mass (M200) than the galaxy line-of-sight velocity dispersion or the richness of the cluster. However, if we exclude clusters embedded in complex large-scale environments, we find that the velocity dispersion of the remaining clusters is as good an estimator of M200 as Lr. The final C4 catalog will contain ∼–2500 clusters using the full SDSS data set and will represent one of the largest and most homogeneous samples of local clusters.