1560s, from galley (n.) in the "ship" sense + slave (n.). The ships were often rowed by slaves or convicts.
gall-bladder
galleon
galleria
gallery
galley
galley-slave
galleywest
Gallic
Gallicism
gallimaufry
gallinaceous