In 2004, Chang made his professional debut with the Sinon Bulls and hit .291/.331/.366. He batted .283/.325/.364 and stole 21 bases in 28 tries in 2005; he was with Sinon as they won the CPBL title. He appeared in the first Konami Cup.
Chang made the Taiwan roster for the 2006 World Baseball Classic and went 4 for 11 with a walk and a double as one of their better performers. In the 2006 CPBL campaign, he hit .284/.335/.365 and only stole 3 bases; the 21 in 2005 was the only time in his first four seasons that he reached double digits in swipes. He was with Taiwan for the 2006 Asian Games and 2006 Intercontinental Cup. In the latter event, he hit .405/.463/.595 with 8 runs, 7 RBI and a surprising 2 home runs in nine games for Taiwan, acting as their main right fielder; Chang only has hit 8 home runs in his first 1,107 at-bats in the CPBL. He tied Sharnol Adriana and Yoandry Urgellés for third in the 2006 Intercontinental Cup with 15 hits, trailing only Alexander Mayeta and Yung-Chi Chen. He tied 8 others, including former major leaguer Ivanon Coffie for second in home runs, trailing only Brad Harman. He failed to make the All-Tournament outfield as Urgellés, Giorvis Duvergel and Frederich Cepeda were chosen.