They did have mining and stone working back then, so that's where I'd start, by mining out a huge underground complex.
In order for the maze to change I'd have big slabs of rock that fit into pockets in the ceiling, and that could be raised and lowered at random.
By using counter weights, possibly by linking two slabs so that one goes up while the other goes down, you could make it so that it wouldn't take that much effort to move them under normal conditions, and then by using water power, possibly with a tipping bucket system or something similar to give it some randomness, you could cause the slabs to shift without any human involvement.
You could also go the other way, by having the slabs set in the floor, and then raising them using water flowing through channels and filling pockets that float the slabs up to block the passage. The downside of this is what it would take to raise a several ton slab of rock.
Maybe if the rock was pumice then it would float naturally and be a lot lighter too, but pumice is soft enough that digging through it wouldn't be hard. It could be pumice faced with granite or metal.
Considering the pyramids were built around 4000 BC, this kind of rock cutting and shaping would have been technically possible with enough skilled workers, and especially if they already had a mine started to start with.
The handwavyness comes in with the idea that this setup could exist for 6000+ years without crumbling to dust, but it is possible.
EDIT:
One way that it could exist for that amount of time is if it was completely dormant. Take the "slabs raise from the floor and are powered by water channels option"; First make sure that it is in a geographically stable area with zero seismic activity. If the channels are completely drained, the water source blocked off, and the entrance very tightly sealed, the maze would have essentially zero wear and tear, little to no dust or moisture to get in and cause corrosion or gum up the works, and generally be inert. It could at that point exist for a long long time without falling to pieces.
To wake it up, have the door being unsealed be a trigger that unblocks the water and allows it to flow through the channels again, raising some slabs right away, and restarting the randomized sequence.
The important part is that the maze can't make use of any organic materials like wood, rope, etc. since those things would most likely rot away long before the maze was needed again.
EDIT 2:
Just a thought... just because it's old doesn't mean that it has to be completely abandoned. There could be a local tribe that does the required maintenance as part of it's religious rituals for instance.
It is a long time, but it's at least possible that an extremely isolated group could maintain their culture.