Harrop invited the striker for a trial at Colchester United and he was signed by the club. His brother, Kazenga LuaLua, is also a professional footballer, and two of his cousins also play professionally; Yannick Bolasie, and Trésor Kandol. LuaLua joined Colchester United in September 1998. Initially, he struggled to adapt and he preferred going to nightclubs over playing for Colchester, Harrop says, "It took a lot of hard work by the staff at Colchester. Micky Cook, the director of youth, had to spend endless hours with him and [manager] Steve Wignall and then [the next manager] Steve Whitton had to spend a lot of time with him talking him through the tactical side of the game and what his role was within the team". LuaLua scored within four minutes of his debut where he appeared as a substitute in a 3–1 defeat to Chesterfield. In two seasons, he made 68 league and cup appearances for Colchester, 44 starts and 24 substitute appearances, scoring a total of 21 goals. His performances attracted the attention of several Premiership clubs and despite manager Steve Whitton's denial that LuaLua was for sale, LuaLua joined Newcastle United in September 2000 for a fee of £2.25 million. An earlier offer by Newcastle of £300,000 for LuaLua made by former manager, Ruud Gullit, had been rejected, but the much increased bid offered financial security and assistance towards a new ground and was one that Colchester felt they could not turn down. LuaLua had been brought to the attention of Newcastle manager, Bobby Robson, by Mick Wadsworth, assistant-manager at Newcastle United, who was a former manager of Colchester. Robson watched LuaLua before deciding to negotiate the transfer, and said, "I see [LuaLua] as a special talent. He has to learn how to play with the other players but he's a special new talent. He has to be nursed and cherished and taught. But we are buying long-term a very promising talent, a very promising player." LuaLua signed a five-year contract with the club. He made his first-team debut in a 1–0 home defeat to Charlton Athletic in September 2000 and made 23 league and cup appearances for Newcastle in the 2000–01 season without scoring. He scored twice in Newcastle's Intertoto Cup campaign at the beginning of the 2001–02 season but his first Premiership goal did not come until April 2002, when he scored a last-minute winner in a 3–2 away win against Derby County.