La plus ancienne trace de paradoxe est relatée dans la Bible :
« Quelqu'un d'entre eux, leur propre prophète, a dit : « Les Crétois sont toujours menteurs, de méchantes bêtes, des ventres paresseux. » »
l'épître à Tite, Paul de Tarse.
Ce prophète, qui vécu au VII siècle av. J.-C., serait Épiménide le Crétois. Toutefois, cette première formulation du paradoxe du menteur n'est apparue paradoxale que bien plus tard.
Il faut ensuite mentionner la pensée paradoxale du Dao De Jing fondatrice du taoïsme au VI siècle av. J.-C..
Les premiers paradoxes, clairement énoncés comme tels, apparaissent dans l'antiquité grecque et sont l'œuvre de Zénon d'Elée (par exemple: Paradoxe d'Achille ou paradoxe de la flèche). Ils étaient alors appréhendés de manière purement rhétorique. Cependant ils préfigurent et annoncent les sciences physiques et mathématiques.
Par la suite, le paradoxe sera un élément moteur de la science en devenir. Ainsi, chaque discipline balbultiante générera ses paradoxes
La théorie des probabilités, élaborée dès le XVII siècle, est plus particulièrement féconde en paradoxes: Paradoxe de Borel, Paradoxe des anniversaires, ...
La naissance de la physique moderne, au début du XX siècle, entraîna l'apparition de nombreux paradoxes. En physique quantique, le Paradoxe EPR, et celui du chat de Schrödinger, mirent en évidence, l'opposition conceptuelle entre cette physique et la physique classique ; mais aussi, la difficulté (voire l'impossibilité) à "interpréter" la physique quantique. Parallèlement la théorie de la relativité engendra également son lot de paradoxes : Paradoxe de Selleri, Paradoxe d'Ehrenfest, Paradoxe des jumeaux, Paradoxe du train.
Enfin, en mathématiques, certain théorèmes parmi les plus récents (Paradoxe de Banach-Tarski, Paradoxe de Skolem) heurtent l'intuition, et ainsi sont abusivement qualifiés de paradoxe.