Após ficar seis anos sem gravar, Paulinho apresenta um de seus mais sofisticados trabalhos. Bebadosamba foi tão bem recebido por crítica e público que alguns o chamaram de disco da década. Exageros à parte, Bebadosamba conquistou cinco prêmios Sharp (o mais importante prêmio da música brasileira nos anos 90) e deu a Paulinho seu primeiro Disco de Ouro, certamente um de seus discos mais bem –sucedidos. A música Timoneiro, em parceria com Hermínio Bello de Carvalho, entrou da galeria de seus grandes sucessos.