Introduction: Prostate cancer in Indonesia is the $3^{rd}$ ranking cancer among males and the $5^{th}$ rank for their cancer mortality. Prognostic markers that can identify aggressive prostate cancer in early stages and help select appropriate therapy to finally reduce the mortality are therefore urgently needed. It has been suggested that stem cells in the prostate gland have a role in initiation, progression, and metastasis of cancer, although controversy continues to exist. Maintenance of normal stem cell or reserve cell populations in several epithelia including prostate has been shown to be regulated by p63 and alteration of p63 expression is considered to have an oncogenic role in prostate cancer. We hypothesize that the expression of cytoplasmic aberrance of p63 is associated with high ALDH1A1 expression as a cancer stem cell marker, thus leading to progression of prostate cancer. Methods: Using a cross-sectional study during two years (2009-2010), a total of 79 paraffin embedded tissues of benign prostatic hyperplasia, PIN prostatic intraepithelial neoplasia, low and high Gleason score prostate cancer were investigated using immunohistochemistry. Associations between cytoplasmic p63 and ALDH1A1, as well as with pathological diagnosis, were analyzed by Chi-Square test using SPSS 15.0. Links of both markers with cell proliferation rate (KI-67) and apoptotic rate (cleaved caspase 3) were also analyzed by Kruskal-Wallis test. Results: The mean age of patient at the diagnosis is 70.0 years. Cytoplasmic aberrance of p63 was associated with ALDH1A1 expression (p<0.001) and both were found to have significant relationships with pathological diagnosis (including Gleason score), (p=0.006 and p<0.001 respectively). Moreover, it was also found that higher levels of cytoplasmic p63 were significantly associated with the frequency of proliferating cells and cells undergoing apoptosis in prostate cancers (p=0.001 and p=0.016 respectively). Conclusion: p63 cytoplasmic aberrance is associated with high ALDH1A1 expression. These components are suggested to have an important role in prostate cancer progression and may be used as molecular markers.