The two-year estimate to replace the system, which still uses green screens, is better than the original timeline, which put the completion date at three years from now.
Senator Charles Schumer, chairman of the Senate Judiciary Committee's Subcommittee on Administrative Oversight and the Courts, said, "Given that this should be one of the highest priorities that America has, it's still going to take us a couple of years,"
"It seems like an awfully long time, given how important this is.," he added.
Sherry Higgins, who was appointed in March to head Trilogy, the FBI's IT upgrade initiative, agreed that two years was an "extremely long time" but said, "The right solution takes a longer time than to just get a solution."
The FBI was, nonetheless, working to get some upgrades completed quickly, including one to improve the ability of agents to search databases. The FBI's system search engine cannot handle complex searches with multiple words.
Higgins claimed that a lack of documentation for existing systems was one obstacle preventing a speedy implementation.
Trilogy would also link all of its major criminal databases, and Higgins, a former senior IT executive at Lucent Technologies, said talks are under way with other federal agencies to ensure that the systems architecture will facilitate interoperability.
The FBI received about $507m (£321m) for IT this financial year, an increase of 127% from the previous year's budget of $223m (£141m).