A significant need for reliable and accurate cancer diagnostics and prognosis compels the search for novel biomarkers that would be able to discriminate between indolent and aggressive tumors at the early stages of disease. The aim of this work was identification of potential diagnostic biomarkers for characterization of different types of prostate tumors. NotI-microarrays with 180 clones associated with chromosome 3 genes/loci were applied to determine genetic and epigenetic alterations in 33 prostate tumors. For 88 clones, aberrations were detected in more than 10% of tumors. The major types of alterations were DNA methylation and/or deletions. Frequent methylation of the discovered loci was confirmed by bisulfite sequencing on selective sampling of genes: FGF12, GATA2, and LMCD1. Three genes (BHLHE40, BCL6, and ITGA9) were tested for expression level alterations using qPCR, and downregulation associated with hypermethylation was shown in the majority of tumors. Based on these data, we proposed the set of potential biomarkers for detection of prostate cancer and discrimination between prostate tumors with different malignancy and aggressiveness: BHLHE40, FOXP1, LOC285205, ITGA9, CTDSPL, FGF12, LOC440944/SETD5, VHL, CLCN2, OSBPL10/ZNF860, LMCD1, FAM19A4, CAND2, MAP4, KY, and LRRC58. Moreover, we probabilistically estimated putative functional relations between the genes within each set using the network enrichment analysis.