The party was initially known as "National Rule of Law Union" and operated only in the small mountainous locality where Natelashvili hails from.

[8] Despite this, in the 1999 Georgian parliamentary election, the party fell short of the electoral threshold to receive the representation in the parliament.

[7] After the protests developed into the Rose Revolution resulting in the successful removal of then-president Eduard Shevardnadze from power, the Labor Party suffered a blow to its popularity and it lost dozens of activists.

[15] Its electoral programme from this period prioritized fighting "wild capitalism", "dictatorship of transnational companies", and "oligarchic and clan control over the economy".

[5][16] The party promised free healthcare, education and social services, as well as nationalization of strategically important facilities, calling for reversing their privatization of 1990s.

[17][18] By 2010, however, the Labor Party has been described as being "fairly ambivalent on the issue of Russian/Western orientation" and it again proposed military neutrality after the 2008 Russo-Georgian War, presenting it as a genuine independence from both Moscow and Washington.