Seit 1996 ist Olekas Mitglied des litauischen Parlaments. In den Jahren 1990 bis 1992 und noch einmal von 2003 bis 2004 war er Gesundheitsminister Litauens. Im Kabinett von Gediminas Kirkilas übernahm er in den Jahren von 2006 bis 2008 das Amt des Verteidigungsministers des Landes. Nach den Neuwahlen im Jahr 2012 übernahm er dieses Amt noch einmal im Dezember 2012 in der neuen Regierung unter Algirdas Butkevičius. Ab 2015 war er zudem stellvertretender Parteivorsitzender der LSDP, einer der Stellvertreter von Algirdas Butkevičius.[1]
Bei der Spaltung der LSDP über die Frage der Fortführung der Regierungsbeteiligung blieb Olekas auf der Seite der neuen Parteiführung und übernahm im November 2017 den Vorsitz der Rumpf-LSDP-Fraktion im Parlament.[2] Nach der Europawahl in Litauen 2019 war er einer vom zwei Vertretern seiner Partei in Brüssel. Im Rahmen der Europawahl 2024 konnte seine Partei die zwei Mandate verteidigen, Olekas wurde aber trotzdem von einem Parteikollegen, dem ehemaligen EU-KommissarVytenis Andriukaitis, als Abgeordneter abgelöst.