The painted greenling was first formally described in 1862 by the American biologist Theodore Gill with the type locality given as San Francisco.

[4][5] The painted greenling's generic name Oxylebius prefixes oxy meaning "sharp", alluding to the sharper snout of this species in comparison to Zaniolepis, to lebius which Gill did not explain.

However Jordan and Evermann gave their view that lebius is a Synonym of Hexagrammos and is a Greek word for a fish small enough to be cooked in a kettle.

[6] The painted greenling has an elongated, compressed body[7] and a long head with a pointed snout.

Specimens (mainly juveniles) sometimes gain protection from larger predators by living among the tentacles of Cribrinopsis albopunctata or Urticina piscivora sea anemones, which are venomous to other animals but do not harm the painted greenling.