Linguists have abstracted "Protoindogermanic" roots from various ancient languages of the language family. There is no direct evidence for such forms, but even the documented history of languages like ancient Greek shows significant amount of changes of its use, with many changes occuring when Greek was a world language used for communication outside of its native speaker circle (it is actually already a simplification to talk of "Greek" since it is a comparatively diverse collection of island dialects, pronunciations, forms and spellings in ancient times).
The evidence we have of older forms of various Indogermanic languages in ancient times very much suggest that the kind of fixed sentence structure built from an aggregation of clauses is a newer development, with the focus of older language use being on nominal phrasings. Prepositions tended to be optional and/or proper prefixes, with the actual meaning expressed by a much larger case system than the systems used in antique times (antique Latin used ablative and vocative cases regularly, antique Greek had vocative and remains of a locative), typically expressed by suffixes. The case system made it convenient to express meaning not through a verb structure but nominal phrases.
When verbs gained increasing mind share, they got their own share of suffixes for tenses, modes, numeri, times, person. Something like "you two should have started to be a little bit ashamed of yourself" could be expressed in a single word.
Creating utterances as a collection of heavily flected words with little requirement as to order and structure later became more rigid and sentence order and particles like prepositions became much more a part of speech that was considered correct than it were at some point of time.
As opposed to more "archaic" living language like German, English relies very little on flectation and on rather few word suffixes while depending much more on sentence order which is much more flexible in German than in English since English uses it as the main factor conveying the relation of items in a sentence.
So basically the "complex" grammar of ancient languages evolved from a state where single words were extensively modified and aggregated in order to convey complex meanings instead of synthesizing sentences with prescribed structure. The common unit of an utterance became a sentence rather than a noun or nominal phrase.
So the languages you consider complex compared to English started out simple in a different way and evolved into more complexity by adding verbs, sentence structure, prepositions and other stuff. Making much of that mandatory provided redundancy that English took opportunity of to simplify the language again eventually, throwing out the case system and other details (with the exception of their ingrained impact on some core stuff like some verb forms and pronouns).