https://www.etymonline.com/search?q=travail
Maybe I shouldn't be so surprised, since English still has the word "travails".
"Work" on the other hand means action, doing:
https://www.etymonline.com/search?q=work
That's quite a difference: one is something no one wants, and the other is something everyone does.
"Labor" falls on the "travail" side, meaning exertion, pain:
https://www.etymonline.com/search?q=labor