This report describes the iterative development of the PACE protocol. The starting point is a simple challenge-response protocol and the final refinement leads to PACE, a protocol satisfying perfect forward secrecy for a session key as well as mutual agreement for the parties on the session key.