Updated project metadata. Vaccinia virus (VACV) has numerous immune evasion strategies, including multiple mechanisms of inhibition of IRF-3, NF-κB and type I interferon (IFN) signaling. Here, we used highly multiplexed proteomics to quantify >8,000 cellular proteins and ~80% of viral proteins over seven time points spanning the whole course of VACV infection. This identified multiple novel viral targets, including putative natural killer cell ligands and IFN-stimulated genes. The class II histone deacetylase HDAC5 was selectively degraded early during VACV infection. Use of cell lines in which HDAC5 was overexpressed or knocked out showed that HDAC5 restricted replication of both VACV and herpes simplex virus type 1 (HSV-1). By generating a protein-based temporal classification of VACV gene expression, we identified the early protein C6, a multifunctional IFN antagonist, as the factor that targets HDAC5 for proteasomal degradation. Our approach thus identifies both a novel restriction factor and a viral mechanism of innate immune evasion.