Significant improvements have been made to the Moderate Resolution Imaging Spectroradiometer (MODIS) cloud mask (MOD35 and MYD35) for Collection 5 reprocessing and forward stream data production. Most of the modifications are realized for nighttime scenes where polar and oceanic regions will see marked improvement. For polar night scenes, two new spectral tests using the 7.2-_m water vapor absorption band have been added as well as updates to the 3.9-12µm and 11-12-µm cloud tests. More non-MODIS ancillary input data have been added. Land and sea surface temperature maps provide crucial information for mid- and low-level cloud detection and lessen dependence on ocean brightness temperature variability tests. Sun-glint areas are also improved by use of sea surface temperatures to aid in resolving observations with conflicting cloud versus clear-sky signals, where visible and near-infrared (NIR) reflectances are high, but infrared brightness temperatures are relatively warm. Day and night Arctic cloud frequency results are compared to those created by the Advanced Very High Resolution Radiometer (AVHRR) Polar Pathfinder-Extended (APP-X) algorithm. Day versus night sea surface temperatures derived from MODIS radiances and using only the MODIS cloud mask for cloud screening are contrasted. Frequencies of cloud from sun-glint regions are shown as a function of sun-glint angle to gain a sense of cloud mask quality in those regions. Continuing validation activities are described in Part II of this paper.