It is the third cyber attack weapon targeting systems in the Middle East to be exposed in recent years.
Stuxnet attacked Iran's nuclear program in 2010, while a related program, Duqu, named after the Star Wars villain, stole data.
Flame can gather data files, remotely change settings on computers, turn on computer microphones to record conversations, take screen shots and copy instant messaging chats.
The virus was discovered by a Russian security firm Kaspersky lad that specializes in targeting malicious computer code.
It made the 20 gigabyte virus available to other researchers yesterday claiming it did not fully understand its scope and said its code was 100 times the size of the most malicious software.
Kaspersky Labs said the program appeared to have been released five years ago and had infected machines in Iran, Israel, Sudan, Syria, Lebanon, Saudi Arabia and Egypt.
"If Flame went on undiscovered for five years, the only logical conclusion is that there are other operations ongoing that we don't know about," Roel Schouwenberg, a Kaspersky security senior researcher, said.
Professor Alan Woodward from the department of computing at the University of Surrey said the virus was extremely invasive. It could "vacuum up" information by copying keyboard strokes and the voices of people nearby.
"This wasn't written by some spotty teenager in his/her bedroom. It is large, complicated and dedicated to stealing data whilst remaining hidden for a long time," he said.
The virus contains about 20 times as much code as Stuxnet, which attacked an Iranian uranium enrichment facility, causing centrifuges to fail. Iran's output of uranium was suffered a severe blow as a result of the Stuxnet activities.
Mr Schouwenberg said there was evidence to suggest the code was commissioned by the same nation or nations that were behind Stuxnet and Duqu.
Iran's Computer Emergency Response Team said it was "a close relation" of Stuxnet, which has itself been linked to Duqu, another complicated information-stealing virus is believed to be the work of state intelligence.
It said organizations had been given software to detect and remove the newly-discovered virus at the beginning of May.
Crysys Lab, which analyses computer viruses at Budapest University. said the technical evidence for a link between Flame and Stuxnet or Duqu was inconclusive.
The newly-discovered virus does not spread itself automatically but only when hidden controllers allow it.
Unprecedented layers of software allow Flame to penetrate remote computer networks undetected.
Components enable those behind it, who use a network of rapidly-shifting "command and control" servers to direct the virus, to turn microphone into listening devices, siphon off documents and log keystrokes.
Eugene Kaspersky, the founder of Kaspersky Lab, noted that "it took us 6 months to analyse Stuxnet. [This] is 20 times more complicated".
Once a machine is infected additional modules can be added to the system allowing the machine to undertake specific tracking projects.