A striking characteristic of cancer cells is their remarkable phenotypic plasticity, which is the ability to switch states or phenotypes in response to environmental fluctuations. Phenotypic changes such as a partial or complete epithelial to mesenchymal transition (EMT) that play important roles in their survival and proliferation, and development of resistance to therapeutic treatments, are widely believed to arise due to somatic mutations in the genome. However, there is a growing concern that such a deterministic view is not entirely consistent with multiple lines of evidence, which indicate that stochasticity may also play an important role in driving phenotypic plasticity. Here, we discuss how stochasticity in protein interaction networks (PINs) may play a key role in determining phenotypic plasticity in prostate cancer (PCa). Specifically, we point out that the key players driving transitions among different phenotypes (epithelial, mesenchymal, and hybrid epithelial/mesenchymal), including ZEB1, SNAI1, OVOL1, and OVOL2, are intrinsically disordered proteins (IDPs) and discuss how plasticity at the molecular level may contribute to stochasticity in phenotypic switching by rewiring PINs. We conclude by suggesting that targeting IDPs implicated in EMT in PCa may be a new strategy to gain additional insights and develop novel treatments for this disease, which is the most common form of cancer in adult men.