The worldwide COVID-19 pandemic caused by the coronavirus SARS-CoV-2 urgently demands novel direct antiviral treatments. The main protease (Mpro) and papain-like protease (PLpro) are attractive drug targets among coronaviruses due to their essential role in processing the polyproteins translated from the viral RNA. In this study, we virtually screened 688 naphthoquinoidal compounds and derivatives against Mpro of SARS-CoV-2. Twenty-four derivatives were selected and evaluated in biochemical assays against Mpro using a novel fluorogenic substrate. In parallel, these compounds were also assayed with SARS-CoV-2 PLpro. Four compounds inhibited Mpro with half-maximal inhibitory concentration (IC50) values between 0.41 μM and 9.0 μM. In addition, three compounds inhibited PLpro with IC50 ranging from 1.9 μM to 3.3 μM. To verify the specificity of Mpro and PLpro inhibitors, our experiments included an assessment of common causes of false positives such as aggregation, high compound fluorescence, and inhibition by enzyme oxidation. Altogether, we confirmed novel classes of specific Mpro and PLpro inhibitors. Molecular dynamics simulations suggest stable binding modes for Mpro inhibitors with frequent interactions with residues in the S1 and S2 pockets of the active site. For two PLpro inhibitors, interactions occur in the S3 and S4 pockets. In summary, our structure-based computational and biochemical approach identified novel naphthoquinonal scaffolds that can be further explored as SARS-CoV-2 antivirals.