Vaccinia virus (VACV) has numerous immune evasion strategies, including multiple mechanisms of inhibition of interferon regulatory factor 3 (IRF-3), nuclear factor κB (NF-κB), and type I interferon (IFN) signaling. Here, we use highly multiplexed proteomics to quantify ∼9,000 cellular proteins and ∼80% of viral proteins at seven time points throughout VACV infection. A total of 265 cellular proteins are downregulated >2-fold by VACV, including putative natural killer cell ligands and IFN-stimulated genes. Two-thirds of these viral targets, including class II histone deacetylase 5 (HDAC5), are degraded proteolytically during infection. In follow-up analysis, we demonstrate that HDAC5 restricts replication of both VACV and herpes simplex virus type 1. By generating a protein-based temporal classification of VACV gene expression, we identify protein C6, a multifunctional IFN antagonist, as being necessary and sufficient for proteasomal degradation of HDAC5. Our approach thus identifies both a host antiviral factor and a viral mechanism of innate immune evasion.