Paul made his electoral debut in the 1997 Lok Sabha by-election in Ernakulam when he defeated Antony Isaac of Indian National Congress (INC). In 1998, he unsuccessfully contested against George Eden, losing by a margin of nearly 75,000 votes. In the same year, in the byelections to the Assembly, caused by the resignation of George Eden who was the sitting MLA, from the Ernakulam Assembly constituency, Paul defeated Leno Jacob of INC and became a member of the Assembly for the next three years. In the 2001 Assembly elections, he was defeated by K. V. Thomas by a margin of 11,844 votes. In the Lok Sabha byelection held in September 2003, caused by the demise of George Eden, Paul notched up victory by a margin of 23,000 votes over M. O. John. In the 2004 general election, he defeated the Congress candidate by a margin of 70,099 votes.^[1]

Paul has the unique record of contesting six elections within a span of seven years and winning four of them—all from the same constituency and that too as an Independent candidate with allegiance to Communist Party of India (Marxist) (CPI(M)).^[2]

He was a member of the Standing Committee for the Ministry of External Affairs, Consultative Committee for the Ministry of Railways, Committee of Privileges and the Press Council of India.

Sebastian Paul was educated from St. Albert's HSS, Ernakulam, Maharaja's College, Ernakulam and Cochin University of Science and Technology, Kalamassery. He is also well known as a media critic and cultural activist. Presented a media analysis programme Maadhyama Vicharam in Malayalam on Kairali TV every Friday at 7.30 p.m. He is writing a weekly column in Deshabhimani Weekly. Law, Ethics and the Media, published by LexisNexis, is his latest book in English.

Sebastian Paul is an advocate by profession^[1] who was against setting up of a High Court Bench in Thiruvananthapuram, much to the dismay of Bar Association of Thiruvananthapuram.^[3]

• Members of Fourteenth Lok Sabha - Parliament of India website