Widespread evidence points to the existence of an ancient Martian ocean. Most compelling are the putative ancient shorelines in the northern plains. However, these shorelines fail to follow an equipotential surface, and this has been used to challenge the notion that they formed via an early ocean and hence to question the existence of such an ocean. The shorelines' deviation from a constant elevation can be explained by true polar wander occurring after the formation of Tharsis, a volcanic province that dominates the gravity and topography of Mars. However, surface loading from the oceans can drive polar wander only if Tharsis formed far from the equator, and most evidence indicates that Tharsis formed near the equator, meaning that there is no current explanation for the shorelines' deviation from an equipotential that is consistent with our geophysical understanding of Mars. Here we show that variations in shoreline topography can be explained by deformation caused by the emplacement of Tharsis. We find that the shorelines must have formed before and during the emplacement of Tharsis, instead of afterwards, as previously assumed. Our results imply that oceans on Mars formed early, concurrent with the valley networks, and point to a close relationship between the evolution of oceans on Mars and the initiation and decline of Tharsis volcanism, with broad implications for the geology, hydrological cycle and climate of early Mars.