Backtracking and unification (logic variables). The latter builds on the former and is key to some of Prolog's amazing capabilities.

At the price of a couple of headaches. Most programmers need to reverse the way they were thinking about programming when learning Prolog.