1570s, "predestined," from fatal + -ly (2). Meaning "in a deadly manner" is from 1590s.
he was fatally ill equipped for the climb
fatal
fatalism
fatalist
fatalistic
fatality
fatally
fat-back
fate
fated
fateful
father