Abstract The Reionization Era Bright Emission Line Survey (REBELS) is a cycle-7 ALMA Large Program (LP) that is identifying and performing a first characterization of many of the most luminous star-forming galaxies known in the z > 6.5 universe. REBELS is providing this probe by systematically scanning 40 of the brightest UV-selected galaxies identified over a 7 deg 2 area for bright C ii 158 μ m and O iii 88 μ m lines and dust-continuum emission. Selection of the 40 REBELS targets was done by combining our own and other photometric selections, each of which is subject to extensive vetting using three completely independent sets of photometry and template-fitting codes. Building on the observational strategy deployed in two pilot programs, we are increasing the number of massive interstellar medium (ISM) reservoirs known at z > 6.5 by ∼4–5× to >30. In this manuscript, we motivate the observational strategy deployed in the REBELS program and present initial results. Based on the first-year observations, 18 highly significant ≥ 7 σ C ii 158 μ m lines have already been discovered, the bulk of which (13/18) also show ≥3.3 σ dust-continuum emission. These newly discovered lines more than triple the number of bright ISM-cooling lines known in the z > 6.5 universe, such that the number of ALMA-derived redshifts at z > 6.5 rival Ly α discoveries. An analysis of the completeness of our search results versus star formation rate (SFR) suggests an ∼79% efficiency in scanning for C ii 158 μ m when the SFR UV+IR is >28 M ⊙ yr −1 . These new LP results further demonstrate ALMA’s efficiency as a “redshift machine,” particularly in the Epoch of Reionization.