Пример использования эвристической информации при решении задач впервые появился в одной из ранних статей Саймона и Ньюэлла [1419], но само выражение "эвристический поиск" и обоснование применения эвристических функций, которые оценивают расстояние до цели, появились немного позже [932], [1126]. Доран и Мичи [404] осуществили обширные экспериментальные исследования в области применения эвристического поиска к решению ряда задач, в частности задач игры в восемь и игры в пятнадцать. Хотя Доран и Мичи провели теоретический анализ длины пути и "проникновения" (penetrance) (отношения длины пути к общему количеству узлов, исследованных к данному моменту) в процессе эвристического поиска, они, по-видимому, игнорировали ту информацию, которую может предоставить текущая длина пути. Алгоритм А*, предусматривающий использование в эвристическом поиске текущего значения длины пути, был разработан Хартом, Нильссоном и Рафаэлем [623], с некоторыми дальнейшими поправками [624]. Дек-стер и Перл [371] продемонстрировали оптимальную эффективность алгоритма А*.

В указанной выше оригинальной статье, посвященной алгоритму А*, было впервые представлено условие преемственности (consistency condition), которому должны удовлетворять эвристические функции. В качестве более простой замены этого условия Полом [1223] было предложено условие монотонности, но Перл [1188] показал, что эти два условия эквивалентны. Аналоги открытых и закрытых списков использовались во многих алгоритмах, явившихся предшественниками алгоритма А*; к ним относятся алгоритмы поиска в ширину, поиска в глубину и поиска по критерию стоимости [97], [399]. Важность применения аддитивных стоимостей путей для упрощения алгоритмов оптимизации особо ярко была показана в работа Беллмана [97].

Пол [1220], [1223] впервые провел исследования связи между ошибками в эвристических функциях и временной сложностью алгоритма А*. Доказательство того, что работа алгоритма А* завершается за линейное время, если ошибка в эвристической функции ограничена некоторой константой, можно найти в работах Пола [1223] и Гашнига [522]. Перл [1188] развил этот результат, что позволило учитывать логарифмический рост ошибки. Применение "эффективного коэффициента ветвления" в качестве критерия эффективности эвристического поиска было предложено Нильссоном [1141].