In eukaryotic cells, the shortening and removal of the poly(A) tail of cytoplasmic mRNA by deadenylase enzymes is a critical step in post-transcriptional gene regulation. The ribonuclease activity of deadenylase enzymes is attributed to either a DEDD (Asp-Glu-Asp-Asp) or an endonuclease-exonuclease-phosphatase domain. Both domains require the presence of two Mg2+ ions in the active site. To facilitate the biochemical analysis of deadenylase enzymes, we have developed a fluorescence-based deadenylase assay. The assay is based on end-point measurement, suitable for quantitative analysis and can be adapted for 96- and 384-well microplate formats. We demonstrate the utility of the assay by screening a chemical compound library, resulting in the identification of non-nucleoside inhibitors of the Caf1/CNOT7 enzyme, a catalytic subunit of the Ccr4-Not deadenylase complex. These compounds may be useful tools for the biochemical analysis of the Caf1/CNOT7 deadenylase subunit of the Ccr4-Not complex and indicate the feasibility of developing selective inhibitors of deadenylase enzymes using the fluorescence-based assay.