This strikes me as two questions with two completely separate answers:
"How could people that philosophy could exist?" People have a long track record of thinking of things that do not exist and then making them a reality. Consider the idea of men flying, finally realized by the Wright Brothers. Contrawise, there is also a long track record of coining words to describe things that already existed but had no word to describe them. For example, the Germans in WWII had submarines long before the term "submarine" or "U-boat" was used by most English speakers.
"How did philosophy come into existence." This, unfortunately, is a difficult question in that it asks how an idea comes into existence. This is not something which everyone agrees upon. There are many competing solutions. Some might say that philosophy always existed. Others might say it was the result of random firings of neurons. Still others might argue it doesn't exist, and that it is in fact an illusionary distinction with no intrinsic meaning.
One commonality I see within the field of philosophy is a desire to explore uncertainty. Much of philosophy stems from thoughts along the lines of "We assume that X is true. However, if X is true, that implies Y and Z are true, which are contradictory" or "We prove that X is true because Y is true, but we really never proved Y was true, we just assumed that. Can we prove that X is true without assuming Y?" This sort of digging at the basic concepts of thought and language and reality are nearly universal in philosophic efforts. Thus, it may be reasonable to assume that philosophy came about because someone felt the need to question the assumptions they were making.