En agosto de 2001, Paul firma contrato discográfico, con Atlantic Records.