We present first-principles calculations of the electronic and phonon band structure considering electron-phonon coupling in thin Ga and Sb nanowires. A full Brillouin zone analysis of the phonons is performed for the investigation of nanowire structural stability. The examined nanowires show instability while the wave vectors are away from the zone center. Compared with the usual Peierls distortion picture, the unstable transverse phonon modes induce a transition without electronic band-gap opening. Electron-phonon interaction yields orders-of-magnitude changes depending on the nanowire structure.