В самых ранних работах, относящихся к проблематике удовлетворения ограничений, главным образом рассматривались числовые ограничения. Выраженные в виде уравнений ограничения с целочисленными областями определения были исследованы индийским математиком Брахмагуптой в VII веке; их часто называют диофантовыми уравнениями в честь греческого математика Диофанта (около 200— 284 гг.), который в своих исследованиях фактически рассматривал область определения положительных рациональных чисел. Систематические методы решения линейных уравнений путем удаления переменных исследовались Гауссом [527]; истоки подходов к решению ограничений с линейными неравенствами можно найти в работах Фурье [487].

Задачи удовлетворения ограничений с конечными областями определения также имеют долгую историю. Например, одной из старых задач в математике является раскрашивание графа (раскрашивание карты— частный случай данной задачи). Согласно данным, приведенным в [125], гипотезу о четырех цветах (в соответствии с которой любой плоский граф можно раскрасить с помощью четырех или меньшего количества цветов) впервые выдвинул Френсис Гутри, студент де Моргана, в 1852 году. Эта задача не поддавалась решению (несмотря на то, что в некоторых публикациях утверждалось обратное) до тех пор, пока доказательство не было получено с помощью компьютера Аппелем и Хакеном [35].

Специальные классы задач удовлетворения ограничений рассматривались на протяжении всей истории развития компьютерных наук. Одним из самых первых примеров решения таких задач, оказавшим наибольшее влияние, была система Sketchpad [1476], которая решала геометрические ограничения на чертежах и была предшественником современных программ рисования и инструментальных средств САПР. Выявлению того, что задачи CSP представляют собой общий класс задач, мы обязаны Уго Монтанари [1073]. Первые попытки приведения задач CSP высокого порядка к чисто бинарным задачам CSP с помощью вспомогательных переменных были впервые предприняты в XIX веке логиком Чарльзом Сандерсом Пирсом. Соответствующие методы были введены в тематику CSP Дектером [367] и доработаны Бакусом и ван Биком [55]. Задачи CSP с предпочтениями между решениями широко рассматривались в исследованиях по оптимизации; обобщение инфраструктуры CSP, позволяющее использовать предпочтения, приведено в [134]. Для решения задач оптимизации может также применяться алгоритм устранения интервалов [369].