When the Garagem disbanded, Lailson started a new band with Nelo Carvalho (guitar), Eliano Macedo (bass) and Artur Stanford (drums): The Lailson Blues Band, which also had, on thge beginning, the participation of the saxofonist Lima Neto.
Improving the setlist of the previous bands, the LBB developed a musical quality that was kept through the differents line ups of the band.
Misael Barros became the drummer of the group in 1996 and satyed with the band until 2005 when the LBB disbanded.
Some of the best guitar players of Pernambuco played with the LBB like Nelo Carvalho (1996-1997), Lalão (1997), Alexandre Bicudo (1997-1999), Cacau Santos (1999) and Riva Le Boss (2000-2005), as well as some of the best bass players: Eliano Macedo (1996-1999), Mateus Gueiros (1999), Nando Barreto (2000 - 2002) and Jean Elton (2002 - 2005).
Isabela de Holanda and Marília Maciel were part of the LBB as backing vocals from 2000 to 2004.
Special guests played with the LBB like the saxofonist Leo Gandelman (1999) and also the popular fiddle player Mestre Salustiano, a folckloric master of the maracatu, who made a guest appearance wth the band that was recorded live in a song composed for him by Lailson and Pedro "eeevee" Gabriel, "Rabequeando o Blues" (Fiddling the Blues).
On the year 2000, the LBB produced the Rock & Blues Circus, a show that was transmmited live by the TV Guararapes with various guest musicians and which was recorded and presented as the New Year's special of that TV station.
It was with the LBB that Lailson started the Rock & Blues Festivals at the Downtown Pub, an event that lasted eight editions and presented many of the artists who became part of the Recife blues scene.