This depends very much on the safe.
A "fire safe" meant only to protect papers from a house fire would be trivial; the one I have is a fairly soft plastic shell filled with unreinforced concrete; it seals in a fire by the shell melting, effectively welding the safe shut and keeping oxygen away from the papers inside -- they may brown from the heat, but without oxygen they can't ignite or combust. Stone tools could easily defeat the simple lock on one of these, or destroy the hinge.
A more robust office safe made of steel would be a long term project. The stone tools used by most North American natives at the time they were invaded by Europeans were harder material than most steels, so could eventually make a hole or cut in the shell of a common steel safe, but it would require they know the contents are worth the effort to invest literally months of daily effort.
A heavy duty safe, like the kind used in small banks or, in the Old West setting, in frontier Wells Fargo offices or similar, would be a big problem for Native Americans still using their native tools. Metalworking wasn't at all common prior to European colonization, and stone tools are limited to the hardness of quartz. Quartz is harder than any common steel (files from the 19th century couldn't mark it, though there are modern steels that can), but if the office safe would be a multi-month project, getting into an Old West bank safe would be a generational project with the technology Native Americans had before they began obtaining metals from European colonists.