In December 2019, the first cases of a novel coronavirus infection causing COVID-19 were diagnosed in Wuhan, China. Viral Papain-Like cysteine protease (PLpro, NSP3) is essential for SARS-CoV-2 replication and represents a promising target for the development of antiviral drugs. Here, we used a combinatorial substrate library containing natural and a wide variety of nonproteinogenic amino acids and performed comprehensive activity profiling of SARS-CoV-2-PLpro. On the scaffold of best hits from positional scanning we designed optimal fluorogenic substrates and irreversible inhibitors with a high degree of selectivity for SARS PLpro variants versus other proteases. We determined crystal structures of two of these inhibitors (VIR250 and VIR251) in complex with SARS-CoV-2-PLpro which reveals their inhibitory mechanisms and provides a structural basis for the observed substrate specificity profiles. Lastly, we demonstrate that SARS-CoV-2-PLpro harbors deISGylating activities similar to SARS-CoV-1-PLpro but its ability to hydrolyze K48-linked Ub chains is diminished, which our sequence and structure analysis provides a basis for. Altogether this work has revealed the molecular rules governing PLpro substrate specificity and provides a framework for development of inhibitors with potential therapeutic value or drug repositioning.