We have developed a method to identify previously undetected histidine and aspartic acid phosphorylations in a human prostate cancer progression model. A phosphoproteome of our cell line model is presented, with correlation of modified protein expression between the three states of cancer: non-tumorigenic, tumorigenic, and metastatic cells. With the described interaction proteins potentially phosphorylated by NM23-H1, cellular responses to motility and conformational change stimuli would be achievable. We detect 20 novel histidine-phosphorylated (pHis) and 80 novel aspartic acid-phosphorylated (pAsp) proteins with diverse functions, such as metabolism, protein folding, and motility. Our data indicate that pHis and pAsp are much more prevalent than previously appreciated and may provide insight into the role of NM23-H1 and signaling events that are critical for metastasis. Using the described method for detecting histidine and aspartic acid phosphorylations and our prostate cancer progression cell system, the potential function of NM23-H1 in suppressing metastasis with a two-component regulation system is discussed.