Prolog is based on formal logic. The program consists of facts and rules. This sets the way of thinking in Prolog. Its syntax and semantics help you to express the underlying logical relations and assumptions. This contrasts with imperative languages, where your program is a set of statements that are doing some changes to the program state. You still need to know about the logical relations and assumptions, but there is no direct connection to the language syntax and semantics as with Prolog.
This connection requires a good understanding of the underlying logical relations of the problem that you are solving. You cannot write down your solution in Prolog without it. If you know the underlying logical relations, then programming in Prolog is easy, when you do not, it is hard. In the latter case, you are forced to discover those relations.
On a new problem, you are unlikely to know underlying logical relations. By using Prolog, your start will be harder, but you are more likely to discover those relations, and after that, reaching the correct solution will be easier. This is what programming in Prolog feels like.
This is based on my own experience of using Prolog as a generic programming language and the answers from What is the level of difficulty for prolog?.