Interest in the study of marine sponges and their associated microbiome has increased both for ecological reasons and for their great biotechnological potential. In this work, heterotrophic bacteria associated with three specimens of the marine sponge Erylus deficiens, were isolated in pure culture, phylogenetically identified and screened for antimicrobial activity. The isolation of bacteria after an enrichment treatment in heterotrophic medium revealed diversity in bacterial composition with only Pseudoalteromonas being shared by two specimens. Of the 83 selected isolates, 58% belong to Proteobacteria, 23% to Actinobacteria and 19% to Firmicutes. Diffusion agar assays for bioactivity screening against four bacterial strains and one yeast, revealed that a high number of the isolated bacteria (68.7%) were active, particularly against Candida albicans and Vibrio anguillarum. Pseudoalteromonas, Microbacterium, and Proteus were the most bioactive genera. After this preliminary screening, the bioactive strains were further evaluated in liquid assays against C. albicans, Bacillus subtilis and Escherichia coli. Filtered culture medium and acetone extracts from three and 5 days-old cultures were assayed. High antifungal activity against C. albicans in both aqueous and acetone extracts as well as absence of activity against B. subtilis were confirmed. Higher levels of activity were obtained with the aqueous extracts when compared to the acetone extracts and differences were also observed between the 3 and 5 day-old extracts. Furthermore, a low number of active strains was observed against E. coli. Potential presence of type-I polyketide synthases (PKS-I) and non-ribosomal peptide synthetases (NRPSs) genes were detected in 17 and 30 isolates, respectively. The high levels of bioactivity and the likely presence of associated genes suggest that Erylus deficiens bacteria are potential sources of novel marine bioactive compounds.