AS1411 is a quadruplex-forming oligonucleotide aptamer that targets nucleolin. It is currently in clinical trials as a treatment for various cancers. We have proposed that AS1411 inhibits cancer cell proliferation by affecting the activities of certain nucleolin-containing complexes. Here, we report that protein arginine methyltransferase 5 (PRMT5), an enzyme that catalyzes the formation of symmetrical dimethylarginine (sDMA), is a nucleolin-associated protein whose localization and activity are altered by AS1411. Levels of PRMT5 were found to be decreased in the nucleus of AS1411-treated DU145 human prostate cancer cells, but increased in the cytoplasm. These changes were dependent on nucleolin and were not observed in cells pretreated with nucleolin-specific small interfering RNA. Treatment with AS1411 altered levels of PRMT5 activity (assessed by sDMA levels) in accord with changes in its localization. In addition, our data indicate that nucleolin itself is a substrate for PRMT5 and that distribution of sDMA-modified nucleolin is altered by AS1411. Because histone arginine methylation by PRMT5 causes transcriptional repression, we also examined expression of selected PRMT5 target genes in AS1411-treated cells. For some genes, including cyclin E2 and tumor suppressor ST7, a significant up-regulation was noted, which corresponded with decreased PRMT5 association with the gene promoter. We conclude that nucleolin is a novel binding partner and substrate for PRMT5, and that AS1411 causes relocalization of the nucleolin-PRMT5 complex from the nucleus to the cytoplasm. Consequently, the nuclear activity of PRMT5 is decreased, leading to derepression of some PRMT5 target genes, which may contribute to the biological effects of AS1411.