Artificial spin-ice systems are lithographically patterned arrangements of interacting magnetic nanostructures that were introduced as way of investigating the effects of geometric frustration in a controlled manner(1-4). This approach has enabled unconventional states of matter to be visualized directly in real space(5-18), and has triggered research at the frontier between nanomagnetism, statistical thermodynamics and condensed matter physics. Despite efforts to create an artificial realization of the square-ice model-a two-dimensional geometrically frustrated spin-ice system defined on a square lattice-no simple geometry based on arrays of nanomagnets has successfully captured the macroscopically degenerate ground-state manifold of the model(19). Instead, square lattices of nanomagnets are characterized by a magnetically ordered ground state that consists of local loop configurations with alternating chirality(1,20-26). Here we show that all of the characteristics of the square-ice model are observed in an artificial square-ice system that consists of two sublattices of nanomagnets that are vertically separated by a small distance. The spin configurations we image after demagnetizing our arrays reveal unambiguous signatures of a Coulomb phase and algebraic spin-spin correlations, which are characterized by the presence of 'pinch' points in the associated magnetic structure factor. Local excitations-the classical analogues of magnetic monopoles(27)-are free to evolve in an extensively degenerate, divergence-free vacuum. We thus provide a protocol that could be used to investigate collective magnetic phenomena, including Coulomb phases(28) and the physics of ice-like materials.