Selon Donald Knuth, l'algorithme d'Euclide est l'un des plus anciens algorithmes1. Il est décrit dans le livre VII (Proposition 1-3) des Éléments d'Euclide (vers 300 avant JC) sous la forme de l'anthyphérèse. Il est aussi décrit dans le livre X (Proposition 2), mais pour un problème de façon géométrique : comment trouver une « unité de mesure » commune pour deux longueurs de segments. Il procède par soustractions répétées de la longueur du plus court segment sur la longueur du plus long. Cela correspond à une adaptation de la méthode naïve de calcul de la division euclidienne, telle que décrite dans l'article consacré. Pour ce problème géométrique, l'algorithme d'Euclide ne termine pas forcément (dans un langage plus moderne, cela correspond à exécuter l'algorithme d'Euclide pour des nombres réels).