Sustainable management of fisheries has proven to be a daunting exercise for Lake Victoria. Exploitation patterns in the fishery are driven by fishers who adopt different strategies as a response to changing economic, management, socio-economic, and resource conditions. Fisheries managers, however, seldom consider these changes in management policies. The aim of the study, therefore, was to evaluate the adaptation strategies of the Nile perch gillnet fishers on Lake Victoria in Uganda using 8-year catch and effort data collected in the period from 2005 to 2015. Trends of the selected effort and catch variables in the study period identified two adaptive fishing strategies by gillnet fishers on the lake. The first group, the paddled fishermen whose gillnet use varied in the first half of the study, diverted to harvesting juvenile Nile perch by using smaller, mesh sizes, monofilament nets and gillnets of less depth in the second half of the study. Motorized fishers, on the other hand, maintained their mesh size, using multifilament gillnets, however, they increased the depth of their nets in the second half of the study period to maintain their targeted fish size. Fishers on Lake Victoria adapted strategies to cope with their constraints and opportunities based on the Nile perch population structure and their economic needs. It is important for fishery managers to consider that the fishers are an integral part of the fisheries ecosystems, and considering their behavior in management decisions will aid in devising adaptive policies for sustainable resource use and sustainable livelihood development of the fishers’ communities.