The earliest particular reference to icons that I recall are in the writings of the mid 4th century Church historian Eusebius. He was personally ambivalent about them in private homes, but the manner of his discussion suggests they were well established if not as widely used as they later came to be in the Church. He also mentions the image reputed to have been made by Christ himself and kept in the city of Edessa.
The image of the Holy Mandylion, is based upon the image Christ made on the cloth and sent to the king of Edessa. Some have suggested that the image as it currently exists was modeled more directly on the image placed upon the door of the chest/box in which the cloth image was kept.
The icons of the Saints derive from Palastinian and Egyptian funerary tradition. It was the custom to make a portrait of the deceased and attach to the body, and then placed as a kind of grave marker at the crypt where the body was buried. There was a mystical connection that was believed to exist between the image and the deceased person. When the body had decomposed, the bones were gathered and placed in a ossuary and the image went with the bones. As Christians from the region died both of natural causes and of martyrdom, their images were gathered with their bones as well. But for martyrs, their bones were brought back into the temples for the veneration of the faithful, and so did their images which were mounted over or near their holy relics. The idea of a connection between the prototype and the image remained and was refined within the context of Orthodox anthropology and theology with respect to liturgical practice. In short enough time visitors would copy the images of saints found in the temples of the place of their martyrdom and take them back to their temples and so the iconographic tradition of the images of the saints was born.
This particular phase was historically quite important for in it are found a number of the theological arguments for them which were used and refined by later generations. If you examine such icons of master iconographers closely, one can see how much of the early Egyptian influence still remains, both materially, and in the geometries of the division of space in the plane of the icon. It has long been argued that Orthodox icons are the material and imagistic heirs of the hieroglyphs of the ancient Egyptians…that as icons they are in fact a species of hieroglyph.
With respect to image of Christ and others the interim phase of the 2nd century was marked by coded symbols sometimes drawn from/evocative of Greek mythology. For example, the later icon of Christ Enthroned borrows the seated posture of Zeus as sculpted in one of the major pagan temples of the time). Occasionally one also sees Apollos-like figures that are meant to point to Christ. These are not icons, but they are moving in that direction in that they served metaphorical roles for the faithful. This is the era of the fish symbol and the anchor and all that, but it was also the time of two particular and widespread anthropomorphic figures, one was called the "Orans" the worshiper. It is the figure of a woman with her arms uplifted in prayer. This is the image retained and symbolically enlarges as the icon we see in the apse of most Orthodox temples, the Theotokos with arms upraised and Christ appearing as a child in a mandorla from her bosom. This represents the moment of the incarnation where Christ took on human form in Mary's womb. The second image is that of the good shepherd where in one sees a man with a flock gathered about him, or a man bearing a sheep upon his shoulders. This of course references Christ.
What seems pretty certain from the record is that the use of the Cross as a venerable symbol of Christ and the faith happened pretty early…early enough to become a universal Christian symbol from the Mar Thoma Christians of India to the first Breton Churches in what is now Southern England. The other images, of Christ and the Theotokos, and the saints while present from very early days began and remained as a number of what were initially local/regional traditions (like certain feast days) that later gained acceptance throughout the rest of the Church.
As for the use of icons prominently in Church architecture, that was beginning around the time of Eusebius and was well underway by the time of St. John Chrysostom. What happened was that the edict of toleration removed most to the threat associated with becoming a Christian…and indeed it became fashionable to become a Christian, and to baptize one's children, etc. So fairly soon…less than a generation after the edict we had temples filled with not only Christians in good standing, but inquirers, catechumens, and lapsed Christians at every stage of repentance…we even had just the idly curious. And since the end of the persecutions it had become more and more common for the Liturgy of the Word and the Divine Liturgy to be held one after the other at the same place with the same people in attendance. Prior, when the Deacon has called out "The Doors, the Doors" the only ones left were baptized Christians in good standing. Essentially everyone there communed in the altar (or what would formally become the altar architecturally). That was not possible in the services with crowds in attendance, which meant unworthy eyes were left to gaze upon Holy Things originally belonging only to the knowledge of the faithful. (Holy Things for the Holy). So in order to assist the deaconate in guarding the altar, and still communicate the Holy mystery in ways permissible to the uninitiated, the guard rail of the altar grew into a framework which supported a curtain that could be drawn and pulled back at appropriate places in the service. In Palestinian lands the embroidery on these early on became very detailed, and often iconographic. In Greek Churches this curtain is still preserved above the Holy Doors, but the rest of the framework became a lattice, and then later a wall (by 15th century Russia). Upon this lattice/wall images of Christ, the Theotokos, the Forerunner, Archangels or Sainted Deacons, and the icon of the namesake of the temple were placed. Then were added ranks of feast days, then ranks of prophets and apostles, and so on until the iconostas we know today came into existence. In western Europe the frame (Roodscreen) never became an iconostasis and retained the function of bearing a curtain. This curtain was generally done away with by the 16th or 17th century under the influence of emerging Protestant sensibilities.