The principles underlying the assembly and structure of complex microbial communities are an issue of long-standing concern to the field of microbial ecology. We previously analyzed the community membership of bacterial communities associated with the green macroalga Ulva australis, and proposed a competitive lottery model for colonization of the algal surface in an attempt to explain the surprising lack of similarity in species composition across different algal samples. Here we extend the previous study by investigating the link between community structure and function in these communities, using metagenomic sequence analysis. Despite the high phylogenetic variability in microbial species composition on different U. australis (only 15% similarity between samples), similarity in functional composition was high (70%), and a core of functional genes present across all algal-associated communities was identified that were consistent with the ecology of surface- and host-associated bacteria. These functions were distributed widely across a variety of taxa or phylogenetic groups. This observation of similarity in habitat (niche) use with respect to functional genes, but not species, together with the relative ease with which bacteria share genetic material, suggests that the key level at which to address the assembly and structure of bacterial communities may not be “species” (by means of rRNA taxonomy), but rather the more functional level of genes.