Most genomes, including yeast Saccharomyces cerevisiae, are pervasively transcribed producing numerous non-coding RNAs, many of which are unstable and eliminated by nuclear or cytoplasmic surveillance pathways. We previously showed that accumulation of PHO84 antisense RNA (asRNA), in cells lacking the nuclear exosome component Rrp6, is paralleled by repression of sense transcription in a process dependent on the Hda1 histone deacetylase (HDAC) and the H3K4 histone methyl transferase Set1. Here we investigate this process genome-wide and measure the whole transcriptome of various histone modification mutants in a Δrrp6 strain using tiling arrays. We confirm widespread occurrence of potentially antisense-dependent gene regulation and identify three functionally distinct classes of genes that accumulate asRNAs in the absence of Rrp6. These classes differ in whether the genes are silenced by the asRNA and whether the silencing is HDACs and histone methyl transferase-dependent. Among the distinguishing features of asRNAs with regulatory potential, we identify weak early termination by Nrd1/Nab3/Sen1, extension of the asRNA into the open reading frame promoter and dependence of the silencing capacity on Set1 and the HDACs Hda1 and Rpd3 particularly at promoters undergoing extensive chromatin remodelling. Finally, depending on the efficiency of Nrd1/Nab3/Sen1 early termination, asRNA levels are modulated and their capability of silencing is changed.