Molecular descriptors capture diverse structural information of molecules and are a prerequisite for ligand-based similarity searching. In this study, we introduce topological matrix-based descriptors to virtual screening for hit discovery. We evaluated the usefulness of matrix-based descriptors in a retrospective setting and compared them with topological pharmacophore descriptors. Special attention was given to the influence of data pre-processing and the applied similarity metric on the virtual screening performance. Overall, the MB descriptors showed a competitive and complementary performance to other descriptors. A prospective screen of a commercial compound library led to the discovery of a novel natural-product-derived cyclooxygenase-2 inhibitor predicted to interact differently with the target protein compared to the query compound ibuprofen. The results of our study motivate the use of matrix-based descriptors for molecular similarity-based virtual screening and scaffold hopping.