Marine sponges harbor diverse microbial communities that represent a significant source of natural products. In the present study, extracts of 21 sponge-associated bacteria were screened for their antimicrobial and anticancer activity, and their genomes were mined for secondary metabolite biosynthetic gene clusters (BGCs). Phylogenetic analysis assigned the strains to four major phyla in the sponge microbiome, namely Proteobacteria, Actinobacteria, Bacteroidetes, and Firmicutes. Bioassays identified one extract with anti-methicillin-resistant Staphylococcus aureus (MRSA) activity, and more than 70% of the total extracts had a moderate to high cytotoxicity. The most active extracts were derived from the Proteobacteria and Actinobacteria, prominent for producing bioactive substances. The strong bioactivity potential of the aforementioned strains was also evident in the abundance of BGCs, which encoded mainly beta-lactones, bacteriocins, non-ribosomal peptide synthetases (NRPS), terpenes, and siderophores. Gene-trait matching was performed for the most active strains, aiming at linking their biosynthetic potential with the experimental results. Genetic associations were established for the anti-MRSA and cytotoxic phenotypes based on the similarity of the detected BGCs with BGCs encoding natural products with known bioactivity. Overall, our study highlights the significance of combining in vitro and in silico approaches in the search of novel natural products of pharmaceutical interest.