Absolutely! I have two memory palaces so far. (I take photos of places and keep them in a folder, and also list each room and the objects in each room in an excel file. This combo helps me to quickly memorize the memory palace. I’ll also use it to help with memorizing whatever I’m trying to memorize.). The PAO and memory palaces play different roles so I believe you need both.
There’s a discussion group on memory palaces in the Art of Memory, which I suggest you check out. I just discovered they also have software to help build memory palaces and there’s a web site (I can’t find it now) that helps you build them. The website is free, though I haven’t used it yet.
The first time I tried to use a memory palace I didn’t appreciate that it really does take work, both the create the memory palace and to place things in it for recall. However, the work is more fun than rote memorization, it takes less time than rote memorization, and the memories are far stickier than rote memorization.