Gimė 1953 m. rugpjūčio 23 d. Vilniuje.

1971 m. baigė Šiaulių 2–ąją vidurinę mokyklą.

1971 m. įstojo į Vilniaus universiteto Teisės fakultetą, kurį 1976 m. baigė ir įgijo teisininko specialybę.

1976–1979 m. dirbo Kaišiadorių rajono prokuratūroje tardytoju, 1979–1982 m. – Kaišiadorių rajono prokuratūroje prokuroro pavaduotoju.

1982–1987 m. – Varėnos rajono prokuroras.

Būdamas 34 metų, 1987 m. paskirtas Lietuvos generalinio prokuroro pavaduotoju, kuriuo dirbo iki 1990 m.

1990–1995 m. – Lietuvos Respublikos generalinis prokuroras. Lietuvoje dar veikiant SSRS generalinei prokuratūrai vyko principinė kova. Buvo siekiama savarankiškos Lietuvos generalinės prokuratūros pripažinimo. Generaliniam prokurorui reikėjo sugebėti išsaugoti valstybėje tvarką ir kartu iš naujo kurti teisėsaugos sistemą. Jis pirmasis prokuratūros sistemoje sukūrė padalinius kovai su organizuotu nusikalstamumu. Per gana trumpą laikotarpį buvo išaiškintos stambios nusikaltėlių grupuotės, jų vadeivoms iškeltos visą Lietuvą sudominusios bylos.

Palaikė kaltinimą žurnalisto Vito Lingio, nužudyto kriminalinių struktūrų ir korumpuotų politinių jėgų užsakymu, nužudymo ir Lietuvos mafijos vadeivos Henriko Daktaro bylose.

1995–1997 m. – Lietuvos Respublikos generalinio prokuroro pavaduotojas.

Nuo 1997 m. iki išrinkimo į Seimą vertėsi advokato praktika.

1997 m. buvo kandidatas į Respublikos Prezidentus. Piliečių pasitikėjimas jaunu, pradėjusiu karjerą politiku, buvo didelis – jis užtikrintai laimėjo pirmąjį rinkimų turą. Antrajame rinkimų ture surinko daugiau kaip 49 procentus balsų ir tik pusę procento atsiliko nuo pagrindinio varžovo – Valdo Adamkaus.

Pirmajame VIII Seimo posėdyje 2000 m. spalio 19 d. išrinktas Seimo Pirmininku.

2001 m. buvo NATO Parlamentinės Asamblėjos pavasario sesijos, surengtos Vilniuje, organizacinio komiteto pirmininkas.

1998 m. balandžio 25 d. steigiamajame Naujosios sąjungos (socialliberalų) suvažiavime išrinktas šios sąjungos pirmininku. Naujosios sąjungos (socialliberalų) Tarybos narys.

Pomėgiai – literatūra, sportas.

Moka anglų, rusų kalbas.

Žmona Jolanta Paulauskienė studijuoja Vilniaus universiteto Teisės fakultete.

Turi keturis vaikus. Iš pirmosios santuokos – du sūnūs: Andrius – Vilniaus universiteto Teisės fakulteto studentas, Vilius – Vilniaus universiteto Ekonomikos fakulteto studentas. Iš antrosios santuokos – du ikimokyklinio amžiaus vaikai – sūnus Arnas ir dukra Aistė.