Several studies have demonstrated intraspecific variation in fish gill size that relates to variation in dissolved oxygen (DO) availability across habitats. In Lake Nabugabo, East Africa, ecological change over the past 12 years has coincided with a shift in the distribution of introduced Nile perch such that a larger proportion of the population now inhabits waters in or near wetland ecotones where DO is lower than in open waters of the lake. In this study, we compared gill size of juvenile Nile perch between wetland and exposed (open-water) habitats of Lake Nabugabo in 2007, as well as between Nile perch collected in 1996 and 2007. For Nile perch of Lake Nabugabo [<20 cm total length (TL)], there was a significant habitat effect on some gill traits. In general, fish from wetland habitats were characterized by a longer total gill filament length and average gill filament length than conspecifics from exposed habitats. Nile perch collected from wetland areas in 2007 had significantly larger gills (total gill filament length) than Nile perch collected in 1996, but there was no difference detected between Nile perch collected from exposed sites in 2007 and conspecifics collected in 1996.