We describe redMaPPer, a new red sequence cluster finder specifically designed to make optimal use of ongoing and near-future large photometric surveys. The algorithm has multiple attractive features: (1) it can iteratively self-train the red sequence model based on a minimal spectroscopic training sample, an important feature for high-redshift surveys. (2) It can handle complex masks with varying depth. (3) It produces cluster-appropriate random points to enable large-scale structure studies. (4) All clusters are assigned a full redshift probability distribution P(z). (5) Similarly, clusters can have multiple candidate central galaxies, each with corresponding centering probabilities. (6) The algorithm is parallel and numerically efficient: it can run a Dark Energy Survey-like catalog in ~500 CPU hours. (7) The algorithm exhibits excellent photometric redshift performance, the richness estimates are tightly correlated with external mass proxies, and the completeness and purity of the corresponding catalogs are superb. We apply the redMaPPer algorithm to ~10000deg^2^ of SDSS DR8 data and present the resulting catalog of ~25000 clusters over the redshift range z{isin}[0.08,0.55]. The redMaPPer photometric redshifts are nearly Gaussian, with a scatter {sigma}_z_~0.006 at z~0.1, increasing to {sigma}_z_~0.02 at z~0.5 due to increased photometric noise near the survey limit. The median value for |{Delta}z|/(1+z) for the full sample is 0.006. The incidence of projection effects is low (<= 5%). Detailed performance comparisons of the redMaPPer DR8 cluster catalog to X-ray and Sunyaev-Zel'dovich catalogs are presented in a companion paper.