The earliest example of 'paper-folding' was an ancient Egyption map, drawn on a paper like substance and folded into a rectangle, like modern road maps.

Back then, it wasn't possible to create intricate paper folding, because the right paper had not been invented. When the Chinese invented wood pased paper, it became possible to fold the paper more crisply and with more precision (2nd century B.C.) It is not known exactally when it started.