In earlier seasons, they had been known as the Shandong Flaming Bulls (山东火牛), but changed their name at the start of the 2003–2004 season. At the same time they moved their home court from Jinan to Yantai (6 matches) and Dongying (5 matches). For the following 2004–2005 season, they moved again to Taian, but moved back to Jinan for 2005–2006.
In the 2004–2005 season, the Shandong Lions finished in sixth place in the North Division, out of the playoffs. In 2005–2006 they finished fifth, again out of the playoffs.