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). Formerly it was lawful for anyone to kill such a person.
[G]if he man to deaðe gefylle, beo he þonne utlah ["Laws of Edward & Guthrum," c.924]
Meaning "disorderly person living in defiant violation of the law, one living a lawless life" is recorded by 1880. As an adjective, from Old English.