Some customers in different parts of the country complained of total disconnection for several hours, while some suffered constant disconnections every couple of minutes.
Telstra corporate relations manager Libby Lyons said services were back on track this morning after they worked through the night to correct the problem.
The ADSL outage started shortly after midnight yesterday. However, Lyons said only around 10 percent of BigPond customers were affected by it.
"It was a random problem across Australia. It seemed to affect customers who have logged off during the early hours yesterday morning and tried to log on again. Our monitoring system showed that many customers were successful in logging in and that it didn't affect all of the customers," Lyons said.
She added that it took them a while to figure out what the actual problem was. The ADSL outage was a result of a "standard software upgrade" that Telstra has planned to do but "unfortunately caused problems despite very best efforts in testing beforehand."
Lyons encouraged customers who are still experiencing the problem to contact Telstra's help desk.