Дейкстра знаменит своим пониманием того, что математическая логика является и должна быть основой для понимания конструкции компьютерной программы и своим вкладом в математическую методологию. Ему принадлежит идея построения операционных систем как явно синхронизируемых последовательных процессов, формализованной разработки компьютерных программ и интеллектуальные основы управления неопределенностью. Он хорошо известен как автор поразительно эффективного алгоритма поиска кратчайшего пути и как разработчик и кодировщик первого компилятора Algol 60. Он был вдохновенным лидером движения за отмену оператора GOTO в программировании. Дейкстра был прекрасным писателем. Он также на протяжении многих лет регулярно переписывался с сотнями друзей и коллег - не по email, а по традиционной почте. Он всегда предпочитал чернильную ручку компьютеру - в своих научных трудах и в письмах. Дейкстра был известен своим остроумием, красноречием и игрой словами, такой как в его замечании: "Вопрос о том, когда компьютер сможет думать, подобен вопросу о том, когда субмарины смогут плавать"; в его совете начинающим исследователям, которые спрашивали у него, как выбрать тему для исследований: "Делайте только то, что вы можете делать"; и в его лекции по поводу получения Премии Тьюринга: "В качестве инструмента компьютеры будут только легкой зыбью на поверхности нашей культуры. Как интеллектуальный вызов, они не имеют прецедента в истории человечества." Дейкстра обогатил язык компьютерной науки многими концепциями и фразами, такими как структурное программирование, разделение участия, синхронизация, смертельное объятие, обедающие философы, слабейшее предусловие, защищенные команды, запрещенное чудо и знаменитые "семафоры" для управления вычислительными процессами. Оксфордский словарь английского языка цитирует его использование слов "вектор" и "стек" в вычислительном контексте.