It depends on what you mean by "theory of evolution." There were certainly pre-Darwinian theories of evolution (Lamarck, Chambers, others). If you want a secular explanation for complexity you need something that will explain how it comes about without any design. Your options are basically some form of "change from something simpler" (i.e. evolution) or "it just happens to spontaneously click into existence" (which spontaneous generation theories had, though whether those are truly secular is probably debatable). Lamarck is usually considered the first fully-formed pre-Darwinian evolutionary theory, though plenty of people had put out vague and undeveloped suggestions about animals having transformed into others prior to that.

It should be noted that "creationism" was not (and is not) a single monolithic category, either. There was, for example, non-Biblical literalist creationism, like that of Agassiz, which was considered theologically controversial. Agassiz basically thought the Bible was ultimately a metaphor and came up with his own creationist approach that involved lots of things not in the Bible (like ice ages) and much longer time periods than implied in Genesis. That's not secular at all, but it's also scientific to a high degree (his reasoning and research on the Ice Ages was correct, for example).

The best overview of evolutionary theorizing is Bowler's Evolution: The History of an Idea, which goes into all of the above.