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 mu m) and [O iii](88 mu 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 similar to 4-5x 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 sigma [C ii](158 mu m) lines have already been discovered, the bulk of which (13/18) also show >= 3.3 sigma 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 alpha discoveries. An analysis of the completeness of our search results versus star formation rate (SFR) suggests an similar to 79% efficiency in scanning for [C ii](158 mu m) when the SFRUV+IR is >28 M (circle dot) yr(-1). These new LP results further demonstrate ALMA's efficiency as a "redshift machine," particularly in the Epoch of Reionization.