Our closest genetic relative, the chimpanzees, have been observed to fashion themselves tools. That link even has a video showing one doing it, if you are interested in the process.
So most likely this is a behavior that was shared by our common ape ancestor over 7 million years ago. The only real tool innovation early man initially brought to the table (or at least the only surviving one in the fossil record) is that he seemed to be really into creating rock tools with chipping. Currently the oldest known examples are from about 3.3 million years ago.
Chimps and bonobos will use stone tools, but they haven't been observed systematically setting out to make themselves better stone tools by chipping off bit of stone. They will improve sticks to make tools, but not rocks (that we've seen).
Considering our species' lofty self-image, it doesn't seem like such a huge step to me.