By Alastair Lawson
BBC News Online South Asia
The rebels control large swathes of rural Nepal
It is estimated that they now have between 10,000 to 15,000 fighters, and are active across the country, with many parts completely under their control.
So how did the rebels transform themselves from a small group of shotgun-wielding insurgents in 1996 to the formidable fighting force they are today?
The disillusionment of the Maoists with the Nepalese political system began after democracy was re-introduced in 1990.
Shining Path
Many who are key figures in the rebel movement today played a role alongside mainstream political parties in over-throwing Nepal's absolute monarchy.
Although they participated in the country's first parliamentary elections, their disenchantment with ceaseless political squabbling - and their anger at the plight of the rural poor - prompted them to take up arms.
In doing so, there is little doubt that the two key rebel leaders, Prachanda and Baburam Bhattarai, derived their inspiration from Peru's Shining Path rebels.
The Maoists military strength has increased considerably in recent years
Both men wanted to emulate the Shining Path's stated objective of destroying government institutions and replacing them with a revolutionary peasant regime.
As with the Shining Path, Nepal's Maoists deal with dissent ruthlessly. Human rights groups say that like the security forces, they are guilty of numerous summary executions and cases of torture.
The Nepalese Maoists have also made some "homegrown" modifications to Maoist ideology.
Caste resentment
They argue that what makes them different from other communist parties in the country is that they want a complete revamp of the multiparty democratic system as part of a programme aimed at turning the country into a Marxist republic.
But on this issue there is some ambiguity, because in the past Maoist negotiators have hinted that they will abandon this demand so that the peace process can be kick-started.
So powerful have the Maoists become that few dare defy their call for a general strike in Kathmandu
In fact the only area where they have stayed consistent is in their demand for an end to Nepal's constitutional monarchy.
Another key grievance of the rebels was the resentment felt by lower caste people against the authority wielded by the higher castes.
The Maoists say that the reason they have so much support is because most of their supporters have traditionally been treated as second-class citizens or worse.
Many analysts that this is the real explanation as to why such a seemingly anachronistic movement has made such dramatic headway.
The rebels can now threaten Kathmandu itself
Unquestionably there is a substantial number of people in Nepal who see the Maoists as the only genuine alternative to the old, repressive social order.
The first Maoist attack is believed to have taken place in 1996, when six government and police outposts were attacked simultaneously in mid-western Nepal. Similar attacks took place on a regular basis in the same area over the next few years.
Initially the rebels were not taken seriously at all by the government, diplomats, journalists or the all-pervasive aid agencies that dominate Nepal's economy. They were lightly armed and not considered a genuine military threat.
Rebel abductions
But since then they have become one of South Asia's most potent rebel groups, rivalling the Tamil Tigers of Sri Lanka.
Today the Maoists are well organised, and the firepower at their disposal greater than ever.
Rifles and explosives have been stolen from captured police outposts and it is believed that the country's open border with India has made it easier to smuggle arms and money.
While many support the Maoists, others are fearful of them
So powerful have the Maoists become that few dare defy them when they call a general strike in Kathmandu. The rebels' threat to cut off the city from the rest of the country can no longer be considered an idle threat.
Only a few weeks ago, the rebels abducted hundreds of school children for a week long "re-education" course on Maoist ideology right under the noses of the security forces on the outskirts of Kathmandu.
The Maoists may not yet have the strength to win their "People's War" but they are too strong to lose it.
As one analyst put it, the government appears to be caught in a classic catch-22 situation.
Until there is substantial social and economic development in the areas of the countryside where the Maoists hold sway, the insurgency will continue.
But development cannot happen until the government gains even limited access to these areas, and access can only be achieved by using highly unpopular and potentially counterproductive military means against a well-organised guerrilla army.
Flag of Nepal

Nepal's 10-year civil war has come to a peaceful conclusion with the signing of a historic accord between Prime Minister Girija Prasad Koirala and Prachanda, leader of the Maoist rebel faction that had been fighting for political change. The deal was signed in Kathmandu on Tuesday.

The deal would allow the Maoists into the Nepalese government, and place both Maoist and government weapons under UN scrutiny. The Maoists had been observing a ceasefire since its declaration more than six months previously.

Prachanda said that the peace agreement would end the 238-year old feudal system. He added that his party would work with new responsibility and make new strong Nepal.

Meanwhile, Koirala said that the deal ended the politics of terron and violence and started the politics of co-operation. He thanked Prachanda to find out a peaceful solution in the country.

The government and the Maoist rebels were accused of human rights abuses in fighting that killed more than 13,000 people.

Nepalese king Gyanendra Singh has welcomed Tuesday's peace deal between the government and the Maoist rebels.