Vodafone Hutchison Australia said it has sacked an undisclosed number of staff after weekend reports that unauthorised parties had obtained log-in details to the telco's customer database.
In a statement, the chief executive Nigel Dews said that the incident had also been referred to the NSW Police, although an internal investigation and IT security review was still ongoing.
Dews said that the company would bring forward several security-related initiatives it had planned for this year.
"We will also be conducting an additional independent security review," Dews said.
The telco also faced a probe from the Australian Privacy Commissioner, which Dews said Vodafone would cooperate fully with.
Vodafone had allowed retail and dealer staff to log into the telco's Siebel CRM system that contained the names, dates of birth, PIN, drivers license numbers and addresses of about four million users.
However, news reports alleged that log-ins to the system had fallen into the wrong hands, allowing external parties - including journalists - the ability to search Vodafone's customer database.
Criminal groups were reportedly paying for Vodafone customer information, while other people used the database to "check their spouses' communications", according to the initial news reports.
Vodafone denied the information was ever publicly available and also moved to reassure customers that their credit card details were "securely protected".
-1.jpg&w=100&c=1&s=0)
.png&w=100&c=1&s=0)
