Regulatory elements in the 3' untranslated regions (UTRs) of eukaryotic mRNAs influence mRNA localization, translation, and stability. 3'-UTR length is determined by the location at which mRNAs are cleaved and polyadenylated. The use of alternative polyadenylation sites is common, and can be regulated in different situations. I present a new method to identify cleavage and polyadenylation sites (CSs) at the genome-wide level. The approach is strand-specific, avoids RNA enzymatic modification steps that can introduce sequence-specific biases, and uses unique molecular identifiers to ensure that all identified CS originates from individual RNA molecules. I applied this method to create the first comprehensive genome-wide map of polyadenylation sites of the fission yeast Schizosaccharomyces pombe, comprising the analysis of 2,021,000 individual mRNAs that defined 8,883 CSs. CSs were identified for 90% of coding genes and 50% of ncRNAs. Alternative polyadenylation was prevalent in both groups, with 41% and 45% of all detected genes, respectively, displaying more than one CS. The specificity of the cleavage reaction was gene-specific, resulting in highly variable levels of heterogeneity in 3'-UTR lengths. Finally, I show that for both coding and non-coding genes, the most common regulatory motif associated with CSs in fission yeast is the canonical human AAUAAA sequence.