Multi-walled carbon nanotube (MWCNT)/indium-tin-bismuth (In-Sn-Bi) composite nanostructures in which In-Sn-Bi nanoparticles have been penetrated by the MWCNT arrays were synthesized using a chemical reduction method. The incorporation of 0.6 wt% MWCNTs with high electrical conductivity into the In-based solder resulted in low minimum electrical resistivity (19.9 ± 1.0 µΩ·cm). Despite being reflowed at the relatively low temperature of 110 °C, the composite solder nanostructures were able to form mechanically stable solder bumps on a flexible polyethylene terephthalate (PET) substrate due to the MWCNT arrays with a high thermal conductivity of 3000 W/(m·K) and In-Sn-Bi nanoparticles with a low melting temperature of 98.2 °C. Notably, the composite solder bumps exhibited high flexibility (17.7% resistance increase over 1000 cycles of operation in a bending test) and strong adhesion strength (0.9 N average shear strength in a scratch test) on the plastic substrate because of the presence of mechanically flexible and strong MWCNTs dispersed within the solder matrix materials. These overall properties are due to the improved diffusivity of the composite solder nanostructures by the cover of the In-Sn-Bi nanoparticles along the MWCNT arrays and the network structure formation of the composite solder bumps.