The data is said to help the NSA track individuals, and map who they know, to aid the agency’s anti-terror work.
The "dragnet surveillance" was condemned by digital rights groups who called for the NSA’s snooping efforts to be reined in.
The news comes as Microsoft plans to use more encryption to thwart NSA spying on it and its customers.
The huge database built up by the NSA (National Security Agency) keeps an eye on "hundreds of millions" of mobile phones, said the Post, adding that it let the agency map movements and relationships in ways that were "previously unimaginable".
It added that the vast programme potentially surpassed any other NSA project in terms of its impact on privacy. Information about the programme was in papers released to the Post by whistleblower Edward Snowden.
The spying agency is said to have accumulated so much data, about 27 terabytes according to leaked papers seen by the Post, that it was "outpacing" the NSA’s ability to analyse the information in a timely fashion.
The analysis, via a computer system called Co-Traveler, was necessary as only a tiny fraction of 1% of the data gathered was actually useful in its anti-terror work, said the paper. The analysis is so detailed that it can be used to thwart attempts to hide from scrutiny by people who use disposable phones or only use a handset briefly before switching it off.
The vast majority of the information gathered is said to come from taps installed on mobile phone networks and used the basic location-information that networks log as people move around. Analysing this data helps the NSA work out which devices are regularly in close proximity and, by implication, exposes a potential connection between the owners of those handsets.