This paper considers the theoretical implications of counter-maps as Palestinian contestations of Israeli policies. In geographic scholarship, counter-maps are conventionally regarded as finished representations of a given oppositional stance. Through a case study of Palestinian maps, I explore how hybrid spatial relationships bind people and places, and consider their implications for counter-mapping projects. I suggest that relational cartography offers conceptual leverage to reconsider the both colonial and nationalist logics in mapping. This framing shifts attention from the presupposed representational authority of a map, to how it comes to produce and portray spaces through contingent forces. This essay rests on the premise that maps profitably considered as questions rather than answers. In this way, the inherent inclusions and exclusions of a map constitute part of the analysis from the outset. To carry out the argument, I first draw theoretical work in geography on relational space into the conversation; namely, that places are constituted in their connections to each other in highly uneven and contingent ways, and that cartography is productively considered as relational, contingent and emergent, rather than representational. Second, I explore the history of cartography in Israel-Palestine and locate the emergence of a concerted Palestinian counter-mapping initiative during the Oslo Peace Process. Third, I examine examples from counter-mapping efforts that aim to document the Israeli occupation. Fourth, I consider how two examples of innovative counter-maps could offer compelling avenues of re-imagining the complex economic, political and environmental processes in the area.