The conspiracy theory was started in late 1993 by Achim Held, a student of computer science at the University of Kiel. When driving to Essen he saw a highway exit to Bielefeld was closed due to road construction, and the struck out city name was then interpreted as a sign that there is no such city. He expanded this into the full theory, and after he posted his text to the newsgroup de.talk.bizarre
in May 16, 1994, it quickly grew into German Internet folklore.
The actual source of this conspiracy theory was the dispute between the Bielefeld based Z-Netz and the Usenet, which used incompatible ways to encode the newsgroup postings. Among the serious flame wars the Bielefeld conspiracy marked the funny side of the dispute.
External link
Google archived version of first newsgroup posting (German)