O.E. utlaga "one put outside the law" (and thereby deprived of its benefits and protections), from O.N. utlagi (n.) "outlaw," from utlagr (adj.) "outlawed, banished," from ut "out" + *lagu, pl. of lag "law" (see law).
"[G]if he man to deaðe gefylle, beo he þonne utlah" ["Laws of Edward & Guthrum," c.924]
The verb is from O.E. utlagian. Meaning "one living a lawless life" is first recorded 1880.