The allegations were made in a fax sent anonymously to the company's legal department four weeks ago, according to German news magazine Der Spiegel.
On Monday, Deutsche Telekom said in a statement printed by AP that it had found indications of "illegal and improper use" of phone calls in 2005 and 2006.
The operator has asked a Cologne-based law firm to investigate the claims, and it said it would pursue criminal charges if appropriate.
The German Government, which owns 14.8% of Deutsche Telekom, welcomed the investigation.
The allegations are similar to events at HP two years ago when the company had tried to identify the source of information leaks.
HP revealed that it had secretly examined the private telephone logs of both journalists and employees. At least three of those journalists subsequently sued HP.