Le origini di Praeneste, la città che molti secoli più tardi darà i natali a Giovanni da Palestrina (1525-1594), sono avvolte nel mito, come spesso accade per le città di antica fondazione. Le leggende riportate dagli storici romani  attribuiscono la fondazione ora a Telegono, figlio di Ulisse e della maga Circe, ora a Ceculo, figlio di Vulcano, ora a Prainestos, figlio del re Latino e nipote di Ulisse. Quel che è certo è che l'insediamento dell'antica Palestrina, città di importanza strategica posta allo snodo della Valle del Sacco su di uno sperone del Monte Ginestro nel gruppo dei monti Prenestini, è databile già a partire dall'inizio dell'VII sec. a.c.

Ad ogni modo, quando nel II sec. a.c. venne costruito il tempio della Fortuna Primigenia, la città era un importante centro commerciale e una fiorente città legata all'antichissimo culto della dea Fortuna, divinità protettrice della fecondità e madre nutrice e generatice di tutti gli dei (quindi primigenia). Nell'imponente tempio, la cui struttura che si sviluppa su tre terrazze artificiali fino al santuario vero e proprio, aveva sede un oracolo che, nascosta in un pozzo scriveva frasi o parole su pezzi di legno (sortes); il vaticinio avveniva calando un ragazzo nel pozzo che, nell'oscurità, raccoglieva a caso i pezzi lanciati dall'oracolo (da cui l'espressione estrarre a sorte). In due giorni all'anno, l'11 e il 12 aprile, si svolgeva la festa solenne in onore della Dea in cui a tutti era permesso di consultare l'oracolo.