The CIA told the Clinton administration about ties between Iraq and Al-Qaeda as early as 1996, according to Stephen F. Hayes of The Weekly Standard, who also includes quotes from a news report run by ABC:

The al Shifa [pharmaceutical plant] in Sudan was largely destroyed after being hit by six Tomahawk missiles. John McWethy, national security correspondent for ABC News, reported the story on August 25, 1998:

Before the pharmaceutical plant was reduced to rubble by American cruise missiles, the CIA was secretly gathering evidence that ended up putting the facility on America's target list. Intelligence sources say their agents clandestinely gathered soil samples outside the plant and found, quote, "strong evidence" of a chemical compound called EMPTA, a compound that has only one known purpose, to make VX nerve gas.

Then, the connection:

The U.S. had been suspicious for months, partly because of Osama bin Laden's financial ties, but also because of strong connections to Iraq. Sources say the U.S. had intercepted phone calls from the plant to a man in Iraq who runs that country's chemical weapons program.

As well they should.