STOC was first organised on 5-7 May 1969, in Marina del Rey, California, United States.
Early seminal papers in STOC include , which introduced the concept of NP-completeness (see also Cook-Levin theorem).