Developing countries are endowed with abundant natural resources. They are also more reliant on natural resources given their limited technology and inadequate infrastructural development. Despite the abundance of such resources, many rural communities are struggling over access to natural resources including fish. Fishing households are faced with ever-declining fish catches and combined effort of overexploitation. The impacts have been severe, especially among small scale fishing households. Many artisanal fisher folks have lost their mainstream source of livelihoods and have had to struggle with meeting their daily subsistence. One dominant sources of fishing livelihoods have either collapsed or proving unsustainable for many households. Fishing households are adapting to the declining livelihoods by diversifying and complementing their traditional fish-based livelihoods. Furthermore, the available formal institutions either facilitate or impede full realization of the potential of other sectors. The study examined the coping strategies of artisanal fishing households living on the shores of Lake Victoria, Kenya amidst declining fish stocks. It concludes that many small-scale fishing households have adopted various livelihood strategies such as increased effort in fishing, migration, reliance on remittances, subsistence farming, targeting fish species, sand harvesting, wage employment and localized credit mobilization in form of merry go-rounds. The study recommends that the government needs to put in place sustainable livelihood opportunities to assist fishing households along the shores of Lake Victoria to diversify their survival.