The identification of biomarkers indicating the level of aggressiveness of prostate cancer (PCa) will address the urgent clinical need to minimize the general overtreatment of patients with non-aggressive PCa, who account for the majority of PCa cases. Here, we isolated formerly N-linked glycopeptides from normal prostate (n = 10) and from non-aggressive (n = 24), aggressive (n = 16), and metastatic (n = 25) PCa tumor tissues and analyzed the samples using SWATH mass spectrometry, an emerging data-independent acquisition method that generates a single file containing fragment ion spectra of all ionized species of a sample. The resulting datasets were searched using a targeted data analysis strategy in which an a priori spectral reference library representing known N-glycosites of the human proteome was used to identify groups of signals in the SWATH mass spectrometry data. On average we identified 1430 N-glycosites from each sample. Out of those, 220 glycoproteins showed significant quantitative changes associated with diverse biological processes involved in PCa aggressiveness and metastasis and indicated functional relationships. Two glycoproteins, N-acylethanolamine acid amidase and protein tyrosine kinase 7, that were significantly associated with aggressive PCa in the initial sample cohort were further validated in an independent set of patient tissues using tissue microarray analysis. The results suggest that N-acylethanolamine acid amidase and protein tyrosine kinase 7 may be used as potential tissue biomarkers to avoid overtreatment of non-aggressive PCa.