This work continues our research into developing novel biosensing technologies for early prostate cancer (PCa) diagnostics. The existing PCa diagnostics based on PSA detection (prostate cancer antigene) in blood serum often yield controversial outcomes and require improvement. However, the long non-coded RNA transcript PCA3 overexpressed in PCa patients’ urine is an ideal biomarker for PCa diagnosis. Thus, recent research mainly focuses on developing biosensors for the detection of PCA3. One of the most promising directions in this research is aptamers as bio-receptors for PCA3. We demonstrated the earlier great potential of electrochemical sensors exploiting aptamer labelled with redox group ferrocene. In this work, we use a 227 nt RNA-based aptamer labelled with methylene blue, which offers a higher affinity to PCA3 than commonly used DNA-based aptamers. Also, conditions for immobilisation of aptamers on gold electrodes were optimised, such as different gold electrodes used (interdigitated electrodes and three-electrode assemblies), the electrode’s roughness and polished surfaces, and the concentration of immobilised aptamers. Initial tests were carried out using cyclic voltammograms(CV) measurements and showed a correlation between oxidation/reductions peaks intensities and the concentration of PCA3. This work proved the main concept of the proposed apta-sensing, e.g. the changes of aptamer secondary structure during binding the target (PCA3). In addition, the redox label comes closer to the electrode surface, thus increasing the charge transfer. The lowest recorded concentration of PCA3 in CV measurements was 0.1 nM which was sufficient for medical diagnostics. However, the main focus was on the use of electrochemical impedance spectroscopy (EIS), which offered even high sensitivity in PCA3 detection down to the pM level. The results obtained are very encouraging and constitute a major step towards developing a simple, reliable, and cost-effective diagnostic tool for the early detection of prostate cancer.