(As I started writing the answer I realized that I had previously posted several responses with many of the relevant references - so mostly I am just posting links to those questions. I don't want to retype the relevant authors and texts).
I think the pertinent question is not which came first, but when did they separate. As Gonzo and Conifold both pointed out, the starting point was something that included all three.
But even this question is difficult because we still haven't been able to completely separate them. More specifically the question of what constitutes exactly a science is still an open one, known as the demarcation problem.
I think science came first. A chimpanzee or proto-human eating an unfamiliar berry and getting poisoned might be considered a scientist.
By this account, any organism learning a behavior (as opposed to having genetically programmed innate behavior) is performing science. So a plant that grows in one direction and runs into an obstacle so it starts growing in another direction is performing proto-science too. For your berry consuming homonid to qualify as doing something close the modern concept of science, it would also have to produce a explanatory model and assign some abstract concept to its empirical observations, and for this happen it would have to have a language (or as you say brain complexity). But once you start using such concepts, it becomes hard to classify them as either scientific or religious. An person in ancient Greece observes that the sun moves in a predictable fashion across the sky and uses an abstract entity to explain this. Whether this entity is the god Apollo's Chariot or some mysterious unseen power called 'gravity' is as much a cultural consideration as it is a question of science vs religion. This is why W.V.O Quine famously wrote that the objects of physics and the gods of Homer differ only in degree not in kind. More generally, the fact that we can't avoid referring to unobservable conceptual or metaphysical entities whenever we want to come up with a useful model is one of the main reasons why science is so hard to separate from philosophy and mysticism.
So to recap what Gonzo and Conifold have already said. They all started out as one, then they started to branch out.
If one has to provide a Western historical timeline, then philosophy and religion first separated in ancient Greece, and then science broke off from philosophy in 17th century, with Newton, who was either the last Natural Philosopher, or the first physicist. In the 20th century, some philosophers of science have argued that the separation isn't as obvious as we thought it was post-Newton. While others have claimed that religion are so separated as to be completely non-overlapping (Steven Gould's NOMA concept).
Some past posts which contain relevant references:
See this question Are philosophy and science mergeable today? and this response to the question.
This question Thinkers and scientists opposed to philosophy? and this response.
Also see this question: How would you know if nonobservable entities exist? and this response to it.
On the question of scientists who think philosophy is useless: Why have those scientists who rejected or opposed philosophy, still succeeded? and this response.
For some takes on the relationship between spirituality and science, see this question: Do some of us possess a godsense? and this response to it, as well as William James' Varieties of Religious Experience.
There is also this question: What is the distinction between mysticism and metaphysics? and this response to it.