At the request of DOE's Office of Nuclear Physics (ONP), Brookhaven National Laboratory (BNL) has created this planning document to assemble and summarize a planning exercise that addresses the core scientific thrust of the Relativistic Heavy Ion Collider (RHIC) for the next twenty years and the facilities operation plan that will support this program. The planning work was carried out by BNL in close collaboration with the RHIC user community and within budgetary guidelines for the next five years supplied by the ONP. The resulting plans were reviewed by the BNL High Energy and Nuclear Physics Program Advisory Committee (PAC) at a special RHIC planning meeting held in December 2003. Planning input from each of the four RHIC experimental collaborations was absolutely central to the preparation of this overall Laboratory plan. Each collaboration supplied two key documents, a five-year 'Beam Use Proposal' and a ten-year 'Decadal Plan'.