The vertebrate gut is host to large communities of bacteria, and one of the beneficial contributions of this commensal gut microbiota is the increased nutritional gain from feed components that the host cannot degrade on its own. Fish larvae of similar age and under the same rearing conditions often diverge with regards to growth. The underlying reasons for this could be differences in genetic background, feeding behavior or digestive capacity. Both feeding behavior and digestion can be influenced by differences in the microbiota. To investigate possible correlations between the size of fish larvae and their gut microbiota, we analyzed the microbiota small and large genetically homogenous killifish and genetically heterogeneous cod larvae by Bray-Curtis Similarity measures of 16S DNA DGGE patterns. A significant difference in richness (p = 0.037) was observed in the gut microbiota of small and large killifish, but the overall gut microbiota was not found to be significantly different (p = 0.13), indicating strong genetic host selection on microbiota composition at the time of sampling. The microbiota of small and large cod larvae was significantly different with regards to evenness and diversity (p = 0.0001), and a strong correlation between microbiota and growth was observed.