Fue presidente (2004) del Parlamento de la República de Lituania (o Seimas) y antiguo presidente interino del país tras la destitución del presidente Rolandas Paksas.
Prosigue posteriormente una rápida carrera en el aparato judicial de la República Socialista Soviética de Lituania, que le lleva a ocupar el cargo de procurador general adjunto en 1987.
Es nombrado procurador general en 1990, cargo que abandona en 1995 para dar sus primeros pasos en la vida política desde 1997 junto a su mentor, el comunista renovador Algirdas Brazauskas, que entonces era el presidente de la República.
Durante las elecciones presidenciales de 1998, Brazauskas decide ceder su puesto y apoya a su delfín Paulauskas, que se presenta en la lista del LDDP.
Paulauskas abandona el LDDP para fundar un nuevo partido de centro izquierda, la Nueva Unión (Naujoji sąjunga (socialliberalai) o NS-SL) en 1998.