In this paper, we study the isomorphism problem of Cayley permutation graphs. We obtain a necessary and sufficient condition that two Cayley permutation graphs are isomrphic by a direction-preserving and color-preserving (positive/negative) natural isomorphism. The result says that if a graph G is the Cayley graph for a group $Gamma$ then the number of direction-preserving and color-preserving positive natural isomorphism classes of Cayley permutation graphs of G is the number of double cosets of $Gamma^ell$ in $S_Gamma$, where $S_Gamma$ is the group of permutations on the elements of $Gamma and Gamma^ell$ is the group of left translations by the elements of $Gamma$. We obtain the number of the isomorphism classes by counting the double cosets.