Van der Linden studeerde tot 1970 economie aan de Katholieke Economische Hogeschool in Tilburg. Hij was lid van de Katholieke Volkspartij (KVP) en werd in 1977 lid van de Tweede Kamer namens het CDA. Hierna werd hij in 1986 staatssecretaris van Buitenlandse Zaken in het kabinet-Lubbers II, maar hij viel in september 1988 over de paspoortaffaire. Hij had op dat moment het paspoort in zijn portefeuille en kreeg het verwijt dat hij de Tweede Kamer onjuist had voorgelicht over het testen van het fraudebestendige paspoort. Na zijn staatssecretariaat werd hij wederom Tweede Kamerlid, ditmaal tot 1998. Vanaf 1999 was hij lid van de Eerste Kamer, waar hij, voor hij voorzitter werd, woordvoerder landbouw en voorzitter van de Kamercommissie voor Europese Samenwerkingsorganisaties.
Op 23 januari 2005 werd hij voorzitter van de Parlementaire Assemblee van de Raad van Europa. In die hoedanigheid leverde hij kritiek op de regeringen van Baltische landen, die Russische minderheden in hun land niet als volwaardige burgers behandelen. Er was kritiek op zijn standpunt tegen de verplaatsing uit het centrum van Tallinn van een monument ter ere van het Rode Leger.[1]
Na de verkiezingen voor de Eerste Kamer van 23 mei 2011 en de installatie van de nieuwe Kamer op 7 juni 2011 heeft hij zich niet opnieuw kandidaat gesteld als voorzitter van de Eerste Kamer. Op 28 juni 2011 heeft hij het voorzitterschap overdragen aan VVD'er Fred de Graaf. In 2015 nam hij afscheid van de Eerste Kamer.
Banden met het Kremlin
In 2022 werd geschreven dat Van der Linden jarenlang gelieerd was aan de regering in Rusland. Op kosten van Rusland reisde Van der Linden door Europa en probeerde hij EU-sancties tegen het land te beperken. Ook zou hij nauwe banden hebben gehad met een Russische agent, Valeri Levitski, en in Wenen hebben afgesproken met de Russische extreemrechtse politicus Leonid Sloetski, die destijds op de EU-sanctielijst stond.[2]