1846, from Irish Sile na gcioch, literally "Sheila of the breasts" [OED]. According to modern folklorists, not a Celtic survival, but originating rather in the Romanesque churches of France and northern Spain. Their theories that it is meant to degrade the female body and discourage sexuality, or that it is meant as an apotropaic gesture to ward off the devil, are not entirely convincing.
But I had started out on the quest of the sheela-na-gig, and I was determined to find it.
As I was about to leave, I casually mentioned my search for the sheela-na-gig—and he knew where it was!
Imagine with what a feeling of triumph I stood at last before the sheela-na-gig!