What is the earliest record of using icons to worship God in the Catholic or Orthodox traditions? The question is as simple as the title. I am simply wondering, ‘When is the earliest recorded date of this tradition?’
According to Gibbons:


  the public religion of the Catholics was uniformly simple and spiritual; and the first notice of the use of pictures is in the censure of the council of Illiberis, three hundred years after the Christian aera. Under the successors of Constantine, in the peace and luxury of the triumphant church, the more prudent bishops condescended to indulge a visible superstition, for the benefit of the multitude; and, after the ruin of Paganism, they were no longer restrained by the apprehension of an odious parallel.


It appears that the creeping in of images was long before the schism that brought about the RC and EO traditions -- so though your question apparently concerns post-schism timeline, I hope this answer is relevant.

See also the Catholic Encyclopedia on the Council of Elvira/Elliberis/Illiberis for arguments on dates.