Short Answer
Coming from a naturalized epistemology, the evolution of language is placed within the context of Darwinian evolution and it's modern day theoretical descendants. (Can't help myself.) Language likely began as signals and used shared intention and at some point; theoretically, the study of grammar became a mathematized theory in language under Noam Chomsky and his notions of generative grammar. Philosophically, the idea that thought occurs as a symbolic language is known as the Language of Thought Hypothesis (SEP) and is supported by subvocalization, among other behaviors.
So, to answer your question, language, which requires a grammar, was an outcome of the evolution of man, and therefore at some point, man existed without a proper language, and today, thinking is considered much broader than language use.
From WP:
[W]hen understood in the widest sense, any mental event may be understood as a form of thinking, including perception and unconscious mental processes. In a slightly different sense, the term thought refers not to the mental processes themselves but to mental states or systems of ideas brought about by these processes.
Long Answer
Linguistics
The likely progression of the evolution of language as a form of communication might be best understood as a journey from signals, which most of the higher-ordered animal kingdom participates in, to full-fledged grammars. There is limited, but strong evidence based on the spontaneous appearances of completely new grammars that grammars inhere to the structure of the mind. The appearance of the Nicaraguan Sign Language is probably the strongest case, though the evolution of creoles from pidgins also offers support. A strong argument for the appearance of language from evolutionary thinking has been made by Tomasello in his Origins of Human Communication.
Philosophy of Mind
Since Bertrand Russell, there has been a strong emphasis in philosophy on seeing language as an extension of intentionality and to describe thought using language, particularly propositional attitudes. From The Language of Thought Hypothesis (SEP):
The term “propositional attitude” originates with Russell (1918–1919 [1985]) and reflects his own preferred analysis: that propositional attitudes are relations to propositions. A proposition is an abstract entity that determines a truth-condition.
Philosophically, this means thought has largely been seen in terms of linguistic description and it's language capacity. Alan Turing and his test from the beginning of electronic computation was seen as a proponent of an operational definitional of thought and intelligence that used language to make measure; in fact, in AI research, there were a few decades where thought was largely seen as equivalent with symbolic manipulation, a view most prominently articulated in the physical symbol systems hypothesis of Newell and Simon. But the idea that thought was roughly equivalent with language goes back hundreds of years at least, and is still a somewhat influential idea. Again, from SEP:
Modern proponents of LOTH typically endorse the computational theory of mind (CTM), which claims that the mind is a computational system. Some authors use the phrase “language of thought hypothesis” so that it definitionally includes CTM as one component.
One of the reasons with it's popularity as a hypothesis is that it provides a nice easy condition to differentiate humans from animals, since no animal is in possession of a grammatical language except Homo sapiens. Descartes was famously an advocate of the position that animals weren't capable of thought because of their lack of language use. (See my answer on Quotations from Descartes on Animals as Automata.)
Cognitive Science
Modern AI has seen many victories of 'thinking machines' validated by machine learning (ML) strategies which come from a connectionist perspective while GOFAI has languished somewhat. Many contemporary thinkers believe that human thought is some balance of symbolic and connectionist activity related to the brain. Linguists, for instance, can adduce both Broca and Wernicke's areas as being linguistically specialized portions of the brain, and fMRIs show that thinking occurs all over the brain depending on the task, such as visual activities in the visual cortex, and so on. Philosophically, such non-linguistic modes of thinking have often been subsumed under the idea of philosophical intuitions. John Searle, a philosopher of language, refers to this sort of complicated, non-linguistic activity as the Background in at least several of his works.
Summary
Today, given the state of 2nd-generation cognitive science, many if not most philosophers of language reject the idea that the label 'thought' can be equated completely with language facility instead accepting the notion that language production and use is a specialized activity within thought. Feelings, emotions, instincts, biases, and intuitions play a very important role in human thinking and are decidedly foundational to the use of language as many researches have found, such as Antonio Damasio and his work on the role of emotions in making choices. The idea that human beings are just walking "language machines" has repeatedly fallen flat on its face in AI research, and modern neurology more or less rules this hypothesis out. But still, the power of language cannot be underestimated in thinking, and among educators poverty, linguistic impoverishment, and intelligence are strongly tied together. (Stanford News) This means that though the LOTH hypothesis seems out of place with modern cogntive science, it has an important role in understanding a very important aspect of human thought.