Nanayakkara joined the Lanka Sama Samaja Party (LSSP) as student in 1958. He was elected to parliament at the 1970 parliamentary election, representing Kiriella for the LSSP.
Nanayakkara later left the LSSP and in 1977 joined with other former members of the LSSP, including Vikramabahu Karunaratne, to form the Nava Sama Samaja Party (NSSP). He was the NSSP's candidate in Ehaliyagoda at 1977 parliamentary election but failed to get elected. He was the NSSP's candidate at the 1982 presidential election. He came fifth and last after receiving only 17,005 votes (0.26%).
The Sri Lankan government proscribed the NSSP, Janatha Vimukthi Peramuna (JVP) and Communist Party of Sri Lanka (CP) after the Black July anti-Tamil riots of 1983. Nanayakkara, Karunaratne, Rohana Wijeweera and other left-wing politicians went into hiding until 1985 when the proscription was lifted.
In 1987 the NSSP joined with the LSSP, CP and Sri Lanka People's Party to form the United Socialist Alliance (USA). Nanayakkara re-entered parliament after the 1989 parliamentary election, representing Ratnapura District for the USA.
Shortly before the 1994 parliamentary election Nanayakkara left the NSSP and rejoined the LSSP, one of the constituent parties of the People's Alliance (PA), an alliance of opposition parties. He was chosen as one of the PA's parliamentary candidates for Ratnapura District and duly elected. Later Nanayakkara became critical of President Kumaratunga's policies, such as privatisation and the handling of the civil war. He was suspended from the LSSP in April 1999. A few days later Nanayakkara crossed over to the opposition in parliament.
Nanayakkara then formed a new party called the Left & Democratic Alliance and stood as its candidate, against President Kumaratunga, at the 1999 presidential election. He came seventh after receiving 23,668 votes (0.28%).
The Left & Democratic Alliance was later renamed the Democratic Left Front (DLF). It joined the United People's Freedom Alliance (UPFA), the successor to the PA. Nanayakkara was chosen as the UPFA's mayoral candidate for Colombo at the 2006 local government elections. He was elected to the Colombo Municipal Council but the UPFA failed to gain control of the council. Nanayakkara became the leader of the opposition on the council.
Nanayakkara was chosen as one of the UPFA's parliamentary candidates for Ratnapura District at the 2010 parliamentary election. He was duly elected.
In a heated debate in the Parliament Vasudeva shouted at Prime Minister Ranil Wickremesinghe foul language which went viral over the internet. In a media interview the prime minister called him ‘dried pumpkin’ when asked about the incident. Vasudeva later claimed that his language was unintentional but refused to apologize.
Again in 2017 Vasudeva used profane language and after government MP Harsha de Silva advised him to mind his language Vasudeva began insulting the PM, IGP, Attorney General and the Bribery Department claiming everything is under the Prime minister's buttocks which led to government ministers questioning if he was under Mahinda Rajapaksa's buttocks for whichreplied "That’s okay. That was a blessing. Being under Mahinda’s buttocks was a great blessing.”