Over the last decade, a multidisciplinary approach (merging cognitive science, anthropology and evolutionary psychology) has stressed the fundamental importance of cognitive constraints concerning the complex phenomenon defined as "religion". The main feature is the predominant presence of belief in agent-concepts that display a strong counterfactual nature, in spite of a minor degree of counterintuitiveness. Consistently with the major trend in cognitive science, we contend that agents populating religious beliefs were generated by the same processes involved to infer the presence of ordinary agents. Coherently with the Peircean framework, in which all cognitive performance is considered as a sign-mediated activity, our main point is that those processes of agency detection are characterized at all levels - from the less conscious to the higher ones - by the inferential procedure called abduction. Hence, the very invention of supernatural agents seems to be the result of a particular series of abductive processes that served some other purposes before (i.e. the detection of predators and preys) and whose output was coherent with that of other abductive patterns. Eventually, they would be externalized and recapitulated in the well-known figures of deities, spirits, and so on: thoughts concerning supernatural beings, at first rather vague, were embodied in material culture with the result of fixing them in more stable and sharable representations that could be manipulated and acquired back in the mind in the definitive form.