Recently, there was a book that came out called "The Lost History of Christianity: The Thousand-Year Golden Age of the Church in the Middle East, Asia and Africa - and How It Died" by Phillip Jenkins.
In it, Jenkins states that until the second millenium, the majority of Christians lived outside of Europe. In fact, he states that the Nestorian Catholicos of what is now Iraq actually had the largest flock. This remained true until the Mongol Invasions and the depredations of the invader Tamurlane, who specifically targeted the Asian Christians for eradication.
Unfortunately, I've only read reviews of the book, not the book itself. I'd be interested to pick up a copy and see where he gets his information though.