Archaeologists and cultural heritage experts explore complex data that is often highly interconnected, multifaceted, multi-dimensional, multi-typed and contains uncertain information. Moreover, questions posed by researchers regarding such data are often ill-defined (where it is difficult to guarantee an answer). We argue for new ways to interact with this data, making note that their analysis provides a ‘grand challenge’ for computer science and heritage researchers. We highlight two visions, inspired from the sub-fields of Immersive Analytics and Deep Maps, as enablers for allowing both experts and the general public to interact and explore heritage data. We use prehistoric data as a case study and discuss key technologies that need to develop further, to help accomplish these two visions.