The co-expression of miRNAs and their target proteins was studied on tissue microarrays from different prostate cancer (PCa) patients. PCa of primary Gleason pattern 4 (GP4), lymph node metastases of GP4, distant metastases, and normal tissue from the transitional and peripheral zones were co-stained by fluorescent miRNA in situ hybridization (miRisH) and protein immunohistofluorescence (IHF). The miRNAs and corresponding target proteins include the pairs miR-145/ERG, miR-143/uPAR, and miR-375/SEC23A. The fluorescence-stained and scanned tissue microarrays (TMAs) were evaluated by experienced uropathologists. The pair miR-145/ERG showed an exclusive staining for miR-145 in the nuclei of stromal cells, both in tumor and normal tissue, and for ERG in the cytoplasm with/without co-expression in the nucleus of tumor cells. The pair miR-143/uPAR revealed a clear distinction between miR-143 in the nuclei of stromal cells and uPAR staining in the cytoplasm of tumor cells. Metastases (lymph node and distant) however, showed tumor cells with cytoplasmic staining for miR-143/uPAR. In normal tissues, beside the nuclei of the stroma cells, gland cells could also express miR-143 and uPAR in the cytoplasm. miR-375 showed particular staining in the nucleoli of GP4 and metastatic samples, suggesting that nucleoli play a special role in sequestering proteins and miRNAs. Combined miRisH/IHF allows for the study of miRNA expression patterns and their target proteins at the single-cell level.