C’est chez Hérodote que l’on trouve les premières allusions à la Palestine dans les textes grecs. Cette région n’y est pas évoquée en tant que telle, mais comme simple lieu de passage entre l’empire perse, dont elle est une province, et l’Égypte. Au livre I, 105, c’est en « Syrie Palestine » que le pharaon Psammétique bloque une invasion de Scythes venus du nord. Selon Ph.-E. Legrand, l’éditeur de la C.U.F., « cette expression désigne, chez Hérodote, des parties plus ou moins étendues de ce que nous appelons la Syrie [en 1932] ; le moins qu’elle embrasse est la Terre-Sainte et le pays côtier habité par les Philistins ». Hérodote ne fait pas mention des Juifs, sans doute par ignorance. Cela peut refléter une réalité historique : l’affaiblissement du peuple juif et de son identité spécifique après la déportation à Babylone (597-538). Quant à la mention par Legrand de la « Terre-Sainte », expression chrétienne, elle relève d’une forme caractérisée d’omission autant que d’anachronisme. Parce que la Palestine, à l’époque, est sous mandat britannique ?
Une autre allusion, au livre III, 5, est en rapport avec le passage du roi perse Cambyse, partant conquérir l’Égypte : Ἀπὸ γὰρ Φοινίκης μέχρι οὔρων τῶν Καδύτιος πόλιος ἡ γῆ ἐστι Σύρων τῶν Παλαιστίνων καλεομένων. « De la Phénicie aux confins de la ville de Cadytis, le pays appartient aux Syriens qu’on appelle Syriens de Palestine. » La ville de Cadytis, qui serait celle de Gaza, est désignée par l’historien comme une cité d’importance considérable. Plus que Jérusalem en tout cas, qui est ici absente.
En II, 104, les mêmes Syriens de Palestine reconnaissent avoir appris l’usage de la circoncision des Égyptiens, tout comme les Phéniciens. Phéniciens et Syriens de Palestine sont encore associés en VII, 89, dans les troupes navales qui accompagnent Xerxès pour son expédition contre la Grèce en 480 ; les deux peuples réunis fournissent 300 trières à la flotte perse. Hérodote ajoute ici une précision : Οὗτοι δὲ οἱ Φοίνικες τὸ παλαιὸν οἴκεον, ὡς αὐτοὶ λέγουσι, ἐπὶ τῇ Ἐρυθρῇ θαλάσσῃ, ἐνθεῦτεν δὲ ὑπερβάντες τῆς Συρίης οἰκέουσι τὸ παρὰ θάλασσαν· τῆς δὲ Συρίης τοῦτο τὸ χωρίον καὶ τὸ μέχρι Αἰγύπτου πᾶν Παλαιστίνη καλέεται. « Ces Phéniciens habitaient jadis, à ce qu’ils disent eux-mêmes, sur les bords de la mer Érythrée [la mer Rouge] ; de là, ils passèrent en Syrie, où ils habitent le littoral ; ce canton de la Syrie et tout le pays qui s’étend jusqu’à l’Égypte s’appellent Palestine. »
Le terme grec de Παλαιστίνη, Palestine, a la même origine que Φιλιστῖνοι, Philistins, qui désigne des populations établies à date ancienne sur la frange côtière. Il est clair en tout cas qu’Hérodote ne s’intéresse qu’à cette bordure maritime du Proche-Orient, qui fournit des navires aux Perses et qui laisse passer leurs troupes ; la Palestine, dans son œuvre, n’est qu’une province marginale, sans identité spécifique. Le nom de Jérusalem, Ἱεροσόλυμα,, et l’adjectif Ἰουδαῖος,, Juif, ne semblent pas apparaître en grec avant la traduction des Septante (IIIe siècle av. J.-C.).