Coronavirus disease 2019 (COVID-19) is an ongoing global pandemic with very limited specific treatments. To fight COVID-19, various traditional antiviral medicines have been prescribed in China to infected patients with mild to moderate symptoms and received unexpected success in controlling the disease. However, the molecular mechanisms of how these herbal medicines interact with the SARS-CoV-2 virus that causes COVID-19 have remained elusive. It is well known that the main protease (Mpro) of SARS-CoV-2 plays an important role in maturation of many viral proteins such as the RNA-dependent RNA polymerase. Here, we explore the underlying molecular mechanisms of the computationally determined top candidate, namely, rutin which is a key component in many traditional antiviral medicines such as Lianhuaqinwen and Shuanghuanlian, for inhibiting the viral target-Mpro. Using in silico methods (docking and molecular dynamics simulations), we revealed the dynamics and energetics of rutin when interacting with the Mpro of SARS-CoV-2, suggesting that the highly hydrophilic rutin molecule can be bound inside the Mpro's pocket (active site) and possibly inhibit its biological functions. In addition, we optimized the structure of rutin and designed two more hydrophobic analogs, M1 and M2, which satisfy the rule of five for western medicines and demonstrated that they (M2 in particular) possess much stronger binding affinities to the SARS-COV-2s Mpro than rutin, due to the enhanced hydrophobic interaction as well as more hydrogen bonds. Therefore, our results provide invaluable insights into the mechanism of a ligand's binding inside the Mpro and shed light on future structure-based designs of high-potent inhibitors for SARS-CoV-2 Mpro.