Earlier than that. I was shopping at a Tesco in Tainan in 2001, although by 2004 or so I’d mostly given up as it carried fewer and fewer imported goods.
The thread linked below is from 2002. Next thread below that is about the handover to Carrefour, which seems to have wrapped up in 2006.