Fish is an important commodity that accounts for 40% of animal protein consumption in Nigeria. Due to its perishability, fish must be processed 6 hours after harvest. Fish is commonly processed by smoking, but the process wastes firewood and is hazardous. Charcoal briquettes (CBs) made from agricultural wastes have been identified as a substitute for firewood (FW). This study aimed to investigate the nutritional composition of three fish species—Synodontis membranaceus, Clarias gariepinus, and Labeo senegalensis—smoked using CB, FW, and wood charcoal (WC). The drying capacity and fuel efficiency were also determined. CB induced the highest moisture loss (84.49%) and highest fuel efficiency (i.e., 0.76 fuel consumption rate), and was most cost-effective (N 795). The proximate analysis of moisture, ash, crude lipids, and crude proteins was carried out. Results of smoked C. gariepinus were significantly different (p < 0.05) for all fuels. In smoked L. senegalensis, moisture and crude protein were significantly different, while in S. membranaceus, only ash was not significantly different (p > 0.05). WC-smoked fish retained more proteins than FW and CBs. The iron, zinc, copper, manganese, magnesium, sodium, potassium, and calcium content were investigated in the smoked fish and were not significantly different (p > 0.05) across the fuels. The fuel type did not significantly determine the mineral content. CBs reduced the moisture (< 10%) in the smoked fish, which reduced biological activities that caused spoilage. Lastly, CB smoking is cheaper and has higher fuel efficiency than FW and WC.