Protein degradation by the Ubiquitin-Proteasome System is one of the main mechanisms of the regulation of cellular proteostasis, and the E3 ligases are the key effectors for the protein recognition and degradation. Many E3 ligases have key roles in cell cycle regulation, acting as checkpoints and checkpoint regulators. One of the many important proteins involved in the regulation of the cell cycle are the members of the Histone Deacetylase (HDAC) family. The importance of zinc dependent HDACs in the regulation of chromatin packing and, therefore, gene expression, has made them targets for the design and synthesis of HDAC inhibitors. However, achieving potency and selectivity has proven to be a challenge due to the homology between the zinc dependent HDACs. PROteolysis TArgeting Chimaera (PROTAC) design has been demonstrated to be a useful strategy to inhibit and selectively degrade protein targets. In this review, we attempt to summarize the E3 ligases that naturally ubiquitinate HDACs, analyze their structure, and list the known ligands that can bind to these E3 ligases and be used for PROTAC design, as well as the already described HDAC-targeted PROTACs.