Natives of pre-Columbian Mesoamerica manufactured Amatl (Nahuatl: āmatl, Spanish: amate or papel amate) during the first millenium BCE. This was a form of paper made by boiling the inner bark of several species of trees, particularly fig trees (genus Ficus) such as F. cotinifolia and F. padifolia. The resulting fibrous material was pounded with a stone to produce a stretchy and somewhat delicate paper, colored light brown with corrugated lines.
"Iconography (in stone) dating from the period contains depictions of items thought to be paper. For example, Monument 52 from the Olmec site of San Lorenzo Tenochtitlán illustrates a personage adorned with ear pennants of folded paper." (Wikipedia article on Amatl)