Nanoparticles, including those based on metals, semiconductors, polymers, lipids, and dendrimers are being investigated as therapeutics and imaging agents in advanced cancer disease. Phenotypic changes play an important role in cancer cell survival, progression, and metastasis and changes in intra- and extracellular protein expression patterns and cell polarity contribute to resistance to therapeutics. Investigations into the mechanisms of uptake and intracellular trafficking of nanoparticles in cancer cells are therefore critical for enhancing the efficacy of nanoscale therapeutics and imaging agents. We report that not only are nanoparticles (quantum dots, gold nanoparticles, and polymeric nanoparticles) taken up spontaneously by related human prostate cancer cell lines, but that their intracellular fate is dramatically influenced by the cancer cell phenotype. While nanoparticles were trafficked to vesicles as punctuated structures throughout the cytoplasm in PC3 human prostate cancer cells, they localized at a single, juxtanuclear location (‘dot-of-dots') in PC3-PSMA cells which express the biomarker, Prostate-Specific Membrane Antigen (PSMA) on their surfaces. PC3-flu cells demonstrated trafficking characteristics intermediate to those between PC3 and PC3-PSMA cells; nanoparticles localized in punctuated structures throughout the cytoplasm in addition to forming the ‘dot-of-dots' structure in some cells. Colocalization analysis, using confocal microscopy revealed that the ‘dot-of-dots' formation in PC3-PSMA cells coincided with the localization of transferrin (marker for recycling endosomes), lysotracker (marker for acidic compartments), and the Prostate-Specific Membrane Antigen (PSMA) in these cells. Importantly, the formation of the ‘dot-of-dots' was highly dependent on microtubule polymerization. Following clathrin-mediated, lipid-raft independent, endocytosis, nanoparticle-containing vesicles were trafficked along these tubular structures finally leading to their localization in the proximity of the microtubule organizing center (MTOC) and the nucleus. The above approach was expanded to further investigate the effects of nanoparticle size / surface chemistry and intracellular proteins on the uptake and trafficking in these cells. Our results demonstrate that differences in cancer cell phenotype can lead to large differences in intracellular localization of nanoparticles, which in turn, can have significant impact on the efficacy of nanoscale therapeutics and imaging agents.