Wikipedia says :
The original form of the theorem, contained in a third-century AD book Sun Zi suanjing (孙子算经 The Mathematical Classic by Sun Zi) by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, the Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).
I think the question is in the form of a poem/puzzle about dividing a certain group of soldiers in rows of various sizes, and to prove that you can reconstruct the original number knowing the remainders. Maybe somebody else could give more precise information.
Wikipedia again says that it appears in Fibonacci's Liber Abaci (1202). So that could be the first European instance.
I suggest that you check into Weil's overview of the history of number theory from Hammurapi to Legendre. That book must surely contain something.