http://www.latimes.com/science/sciencenow/la-sci-sn-fossilized-fish-rods-cones-20141223-story.html http://en.wikipedia.org/wiki/Vision_in_fishes http://en.wikipedia.org/wiki/Evolution_of_color_vision It appears that color vision arose some 500,000,000 years BC.
Not entirely surprising - I would assume that a wavelength detection mechanism existed long before what we would even recognize as an "eye". Of course this cannot be backed by the fossil record but it seems the most logical, especially when it is observed that color is an important survival trait to shallow water fish.