According to the Oxford English Dictionary, the speech hesitation "hum" goes at least as far back as 1469. We also find "hem" from 1526, "haw" from 1679, and "er" from 1862. But these are only the first attestations of the words in print. It is likely that they go back much further than that.
Michael Erard, in his book Um...: Slips, Stumbles, and Verbal Blunders, and What They Mean, traces the history of um, and doesn't find any mention of it — or its ancient Greek or Latin equivalent — in classical works on oration, though there is plenty of advice against speaking with hesitancy or lack of fluency. It doesn't appear in court transcripts, or other written records of natural conversation either, until the modern era. With a few exceptions, people didn't really start talking about um, or complaining about it, until the advent of voice recording. It is likely they were using it all along, but they either didn't notice it, or didn't deem it worthy of writing down — it wasn't considered a word, but a noise, like a cough.
Every language has its own version of um. French has euh, Korean eum, Finnish öö, Russian eh; even sign languages have signs for um. The fact that most languages have some kind of um suggests that it serves a natural and important language function.
So what is this important language function? Why do people say um? Not because they are nervous. Scholarly studies of the word reveal that the use of um does not correlate with anxiousness or any particular personality traits. Rather, um is used to signal an upcoming pause — usually uh for a short pause and um for a longer pause. The pause may be needed in order to find the right word, remember something temporarily forgotten, or repair a mistake. Um holds the floor for us while we do our mental work. It buys some time for thinking.