The firm has also cut its sales forecast for the year, warning annual sales would likely fall "modestly below" previous predictions of 50% sales growth.
The VMware share price dived almost 25% on the sacking and sales announcement, part of a 70% slide since last October.
VMware is the market leader in server virtualisation, where companies can run multiple operating systems and demanding applications on a single machine to save on costs.
Greene has been replaced by Paul Maritz, a former senior Microsoft executive who managed the development of Windows 95 and other software releases before he retired from Microsoft in 2000.
EMC, which owns 85% of VMware, was the main instigator of Greene's removal.
EMC and other major investors wanted someone with more experience of running a large and growing company, and said Greene had been offered other roles, but that she had refused to move over.