The flaw has been found in a software component known as Bash, which is a part of many Linux systems as well as Apple's Mac operating system.
The bug, dubbed Shellshock, can be used to remotely take control of almost any system using Bash, researchers said.
Some experts said it was more serious than Heartbleed, discovered in April.
"Whereas something like Heartbleed was all about sniffing what was going on, this was about giving you direct access to the system," Prof Alan Woodward, a security researcher from the University of Surrey, told the BBC.
"The door's wide open."
Some 500,000 machines worldwide were thought to have been vulnerable to Heartbleed. But early estimates, which experts said were conservative, suggest that Shellshock could hit at least 500 million machines.
The problem is particularly serious given that many web servers are run using the Apache system, software which includes the Bash component.Patch immediately
Bash - which stands for Bourne-Again SHell - is a command prompt on many Unix computers. Unix is an operating system on which many others are built, such as Linux and Mac OS.
The US Computer Emergency Readiness Team (US-Cert) issued a warning about the bug, urging system administrators to apply patches.
However, other security researchers warned that the patches were "incomplete" and would not fully secure systems.
Of particular concern to security experts is the simplicity of carrying out attacks that make use of the bug.Analysis - Mark Ward, technology correspondent security image
Shellshock rates a 10 on the scale of vulnerabilities. As bugs go, it's about as bad as it gets.
Except that the last big bad bug, Heartbleed, rated an 11, according to one expert.
That should mean Shellshock isn't as bad. Right?
Maybe. It's too early to tell.
With Heartbleed, more work had been done by the folks that found it so it was easier to estimate who was at risk. There were lots of big targets, many of which had large user populations.
With Shellshock, the sheer number of potential victims is higher. And we do know that an exploit has been produced and some folks are scanning sites to see which are vulnerable to attacks based around that code.
So far, what's keeping servers safe is the fact that cyber thieves are lazy and tend to copy what has already worked. Finding exploits is specialised, hard work so they only tend to pile in once that appears. With that code already in circulation, the early news about Shellshock may just be the first tremor of a much bigger quake.
Cybersecurity specialists Rapid7 rated the Bash bug as 10 out of 10 for severity, but "low" on complexity - a relatively easy vulnerability for hackers to capitalise on.
"Using this vulnerability, attackers can potentially take over the operating system, access confidential information, make changes, et cetera," said Tod Beardsley, a Rapid7 engineer.
"Anybody with systems using Bash needs to deploy the patch immediately."
Security firms have suggested that there is evidence Shellshock is being used by hackers.
"The vulnerability has already been used for malicious intentions - infecting vulnerable web servers with malware, and also in hacker attacks," said Kaspersky Labs.
"Our researchers are constantly gathering new samples and indications of infections based on this vulnerability."
For general home users worried about security, Prof Woodward suggested simply keeping an eye on manufacturer websites for updates - particularly for hardware such as broadband routers.Free questions
The new bug has turned the spotlight, once again, onto the reliance the technology industry has on products built and maintained by small teams often made up of volunteers.
Heartbleed was a bug related to open source cryptographic software OpenSSL. After the bug became public, major tech firms moved to donate large sums of money to the team responsible for maintaining the software.
Similarly, the responsibility for Bash lies with just one person - Chet Ramey, a developer based at Case Western Reserve University in Ohio.
That such key parts of everyday technology are maintained in this way is a cause for concern, said Tony Dyhouse from the UK's Trustworthy Security Initiative.
"To achieve a more stable and secure technology environment in which businesses and individuals can feel truly safe, we have to peel back the layers, start at the bottom and work up," he said.
"This is utterly symptomatic of the historic neglect we have seen for the development of a dependable and trustworthy baseline upon which to develop a software infrastructure for the UK.
"Ultimately, this is a lifecycle problem. It's here because people are making mistakes whilst writing code and making further mistakes when patching the original problems."
Follow Dave Lee on Twitter @DaveLeeBBC