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 ~10,000 deg super(2) of SDSS DR8 data and present the resulting catalog of ~25,000 clusters over the redshift range z isin 0.08, 0.55. The redMaPPer photometric redshifts are nearly Gaussian, with a scatter sigma sub(z) approximately 0.006 at z approximately 0.1, increasing to sigma sub(z) approximately 0.02 at z approximately 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 (< or =, slant5%). Detailed performance comparisons of the redMaPPer DR8 cluster catalog to X-ray and Sunyaev-Zel'dovich catalogs are presented in a companion paper.