We have identified regions in the Martian tropics with anomalously warm nighttime surface temperatures. The seasonal evolution of these anomalies is strongly correlated with the waxing and waning of the tropical cloud belt that is most prominent during Northern Hemisphere summer. We attribute the anomalies to enhanced downward infrared radiation from water ice clouds. The close agreement with spatial maps of atmospheric extinction derived from Mars Orbiter Laser Altimeter radiometry strongly supports this interpretation. We show that a Mars general circulation model simulation with radiatively active water ice clouds is able to reasonably match the observed spatial pattern and amplitude of the surface temperature anomaly. The nighttime clouds are most prominent in the Tharsis and Arabia regions and are thicker (optical depth ~ 1) and more extensive than daytime clouds. Our cloud retrievals are the first to spatially map the nighttime clouds and provide an estimate of their thermal influence.