In Ancient Greek, it is assumed that most, if not all, prepositions were once adverbs. That is why most prepositions can still be used as adverbs starting a sentence in Ancient Greek, as in "upon [that event], the King refused to...". If the same applies to the Germanic languages, it accounts for the existence of our ubiquitous phrasal and separable verbs, which still use "prepositions" in a non-prepositional way. The fact that new phrasal and separable verbs can still be created supports this hypothesis.
On a side note, the preverbial affix e- (the augment) for the past tenses in Ancient Greek probably came from an adverbial constituent *he meaning something like "past" or "then". (There is evidence suggesting that this is cognate to the Proto-Germanic prefix that is used with past participles in German and Dutch, ge-, though others suggest instead that ge- is related to Latin con-, Greek sun-, "together". If the latter, I don't know whether *he- would be related to con-/sun- as well. In any case, Old English used to have ge- as well, the vestiges of which can still be seen in many words, such as a-like (Dutch gelijk) and e-nough (Dutch "genoeg"). For more on the English prefix, see the question What we've gelost.)
It is my theory that most elements of syntax are relatively new (some post-Proto-Indo-European) and originate in separate words that melted with content-words and turned into affixes by clisis (enclisis, proclisis, etc). There is evidence that points to this for inflection: it is believed that, say, the dative ending -i was once a separate word, perhaps some postpositional adverb, which accompanied the direction of an action. Evidence for this might be the use of certain suffixes in Greek that are sometimes interchangeable with cases: -the(n) is mostly a (poetic) suffix of separation, which is normally expressed by the genitive; but it can often take on other functions of the genitive too, such as possession. And there are other suffixes that imitate partial cases: -de for direction (instead of accusative/dative/preposition), -(s)ô approximately for a forward position.
The birth of relative pronouns (classical hos) and demonstrative pronouns (classical houtos) in Ancient Greek is sometimes estimated to be not long before the time of Homer, because, in his epics, there is usually no difference in form between these pronouns and the article; it is often hard to decide on the interpretation of an instance of to (neuter article in classical Attic) or hos (masculine relative pronoun in Attic), when all three options seem possible for each (article, demonstrative, relative). This is evidence that syntax can also develop from differentiation between allophones/allomorphs, or out of nowhere.