"the beaten dog in a fight," 1887, from under + dog (n.). Compare top dog "dominant person in a situation or hierarchy" (see top (adj.)). Its opposite, overdog, is attested by 1908.
I'm a poor underdog
But tonight I will bark
With the great Overdog
That romps through the dark.
[from "Canis Major," Robert Frost, 1928]