Old English utlaga "one put outside the law" (and thereby deprived of its benefits and protections), from a Scandinavian source such as Old Norse utlagi (n.) "outlaw," from utlagr (adj.) "outlawed, banished," from ut "out" (see out (adv.)) + *lagu, plural of lag "law" (see law).
[G]if he man to deaðe gefylle, beo he þonne utlah ["Laws of Edward & Guthrum," c.924]
Meaning "one living a lawless life" is first recorded 1880. As an adjective from Old English.