We know very little about the origin of origami. Some say origami originated in China, and others say in Japan, both without any evidence.
In Japan, we have a custom to wrap things in paper since the HEIAN Era (794-1192). TATOGAMI (different from TATO) was an example. I think, however, they were too simple to be called origami. In the MUROMACHI Era (1392-1573), when they could obtain paper comparatively easily, they came to wrap gifts and add some folds to represent their sincerity. These folding patterns was regarded as a part of etiquette among BUSHI, or samurai warriors, and handed down by Ogasawara School, Ise School, and Kira School. NOSHI was an example of them. They may be the origin of origami in Japan.
In 1797, "SEMBA-ZURU ORIKATA (Thousands of Cranes Origami)" was published in Kyoto, Japan. It's the oldest known origami book in the world. It contains 49 REN-ZURU (connected cranes) models and KYO-KA (short comic poems). The models were designed by a monk of CHO-EN JI temple at KUWANA city named GIDO (pen-name: ROKO-AN). The author is AKISATO RITO. He assembled GIDO's models and published them with his titles and KYO-KA.
Not only Japanese but Chinese and European have origami tradition. Especially, Pajarita (Little Bird) is popular in Spain. Origami was less popular in China and Europe than in Japan. It's partly because Japanese paper WASHI is suitable for origami. Some say it's because Japanese are skillful, but I don't think so. In evidence, origami is getting more and more popular in all over the world.