Question: First Use of the Name Al Qaeda?

A documentary I watched (Power of Nightmares) claimed that the name "Al-Qaeda" did not exist/was not applied to terrorist activities before September 11th. How can I verify this?

Answer: First Use of the Name Al Qaeda?

Doing a simple search of Al Qaeda lead me to this timeline from the BBC news.
http://news.bbc.co.uk/1/hi/world/3618762.stm

They claim that Al Qaeda was formed in 1988, and that the term Al Qaeda means "the base" in Arabic. There is also similar information through this site:
http://www.infoplease.com/spot/terror-qaeda.html