Early detection of prostate cancer is problematic due to the lack of a marker that has high diagnostic sensitivity and specificity. The prostate specific antigen (PSA) test, in combination with digital rectal examination, is the gold standard for prostate cancer diagnosis. However, this modality suffers from low specificity. Therefore, specific markers for clinically relevant prostate cancer are needed. Our objective was to proteomically characterize the conditioned media from three human prostate cancer cell lines of differing origin [PC3 (bone metastasis), LNCaP (lymph node metastasis), and 22Rv1 (localized to prostate)] to identify secreted proteins that could serve as novel prostate cancer biomarkers. Each cell line was cultured in triplicate, followed by a bottom-up analysis of the peptides by two-dimensional chromatography and tandem mass spectrometry. Approximately, 12% (329) of the proteins identified were classified as extracellular and 18% (504) as membrane-bound among which were known prostate cancer biomarkers such as PSA and KLK2. To select the most promising candidates for further investigation, tissue specificity, biological function, disease association based on literature searches, and comparison of protein overlap with the proteome of seminal plasma and serum were examined. On the basis of this, four novel candidates, follistatin, chemokine (C-X-C motif) ligand 16, pentraxin 3 and spondin 2, were validated in the serum of patients with and without prostate cancer. The proteins presented in this study represent a comprehensive sampling of the secreted and shed proteins expressed by prostate cancer cells, which may be useful as diagnostic, prognostic or predictive serological markers for prostate cancer.