Geological observations have revealed that early Martian terrains were carved with by numerous networks of valleys, which provides evidence that prolonged water activity sculpted the ancient surface of Mars during the late Noachian and the early Hesperian ages. Although such geological records would in theory require a large volume of liquid water under a long-term stable “warm and wet” climate, several model studies have indicated a contrasting “cold and icy” climate in early Mars, such that the formation of large-scale ice sheets on highlands would provide a vast reservoir of meltwater. In this study, we developed a global ice sheet model, named ALICE (Accumulation and ablation of Large-scale ICE-sheets with dynamics and thermodynamics) to perform the first simulation of the evolution of ice sheets coupled with a paleo-Mars global climate model. We began our calculations of glacial formation from the initial state with the ocean water amount corresponding to a 500 m global equivalent layer (GEL) for “cool and wet” atmospheric conditions with a surface pressure of 2 bar, H2 mixing ratios of 0% and 3%, and obliquities of 20°, 40°, and 60°. Our results show that all the water of the ocean and lakes were transferred to ice sheets within ~105 Mars years, and extensive ice sheets (thousands of meters in thickness) were formed in the southern low to middle latitudes. When geothermal heat flux was suitably high and the atmosphere contained 3% of H2, continuous subglacial melting supplied enough water due to widespread temperate-based ice sheets, forming runoff systems in the southern highlands where most valley networks are observed. With an obliquity of 40°, meltwater carved early Martian terrains within a relatively brief geological timescale (~105 Mars years). We also revealed that CO2 only atmosphere (H2 mixing ratio of 0%) could not reproduce temperate-based ice sheets and subglacial erosions even with assumed higher geothermal heat fluxes. There is still a possibility that several valleys were produced by short-lived climatic warming events, such as volcanism and meteorite impacts, which could produce the vast amount of meltwater required to sculpt valley systems.