Defense Department officials said that cruise missiles, bombers and submarines had been used in the attack on what was described as a broad range of targets.
President Bush described the attacks, which also involve British forces, as a new front in the operation to combat terrorism.
Explosions and fires were also reported in the northern city of Mazar-e Sharif.
The BBC's Catherine Davis - reporting from opposition-controlled territory in northern Afghanitan - says a huge flash lit up the clear night sky and several dull booms sounded across the plains north of Kabul.
Meanwhile the main target of the attacks, Saudi-born militant Osama Bin Laden, was seen on video believed to be recorded before the strikes making a defiant statement.
He said that the US was "filled with fear from north to south, east to west".
In an address to the US nation, Mr Bush said strikes by US and British forces were taking place against training camps and military installations of the al-Qaeda network in Afghanistan, and that they had been carefully targetted.
Mr Bush said the Taleban would "pay the price" for sheltering terrorists.
(Click here for map of targets)
"In this conflict there is no neutral ground, there can be no peace in a world of terror...," he said. "We did not ask for this mission but we will fulfil it."
He added that the operation would be accompanied by deliveries of food, medicine and other supplies to the people of Afghanistan. UK Prime Minister Tony Blair echoed Mr Bush's words, saying the West would act with "reason and resolve" in its campaign.
The Associated Press quoted a Taleban official in Pakistan as saying that the Taleban was "ready for jihad".
Earlier, the Taleban says it has sent 8,000 troops to its border with Uzbekistan, which has given the US access to an air base for its anti-terrorism campaign.
The US administration has repeatedly rejected Taleban offers to bargain over the fate of its guest, Saudi-born militant Osama Bin Laden.
Background to strikes
The US promised action after terror attacks against the US on 11 September left over 5,600 people dead or missing.
A fourth hijacked plane crashed in Pennsylvania.
The US was quick to name Bin Laden and his al-Qaeda organisation as the chief suspects behind the suicide attacks.
President George W Bush demanded that the ruling Taleban in Afghanistan hand over Bin Laden and other suspects immediately or "share in their fate".
And on Saturday he said that full warning had been given and time was running out.
But despite diplomatic pressure from neighbouring Pakistan, the Taleban refused to expel Bin Laden.
Coalition-building
The US has repeatedly stressed that their actions since the 11 September attacks were not directed against Islam.
He said that "either you are with us, or you are with the terrorists".
UK Prime Minister Tony Blair was one of the first to pledge backing for US efforts.
The Pakistani leader, General Pervez Musharraf, has also offered full support, but he has faced considerable opposition at home from those opposed to any US military action.
Pakistan and Iran have agreed to open their borders to receive refugees from Afghanistan in the event of strikes by American-led forces.
Rumours of possible strikes have led to a major exodus of refugees from Afghanistan.
Two hijacked planes crashed in the twin towers of the World Trade Center in New York, and a third hit the Pentagon in Washington.
President Bush has tried to obtain support from as wide a coalition of nations as possible.
Related to this story:
Bin Laden warns US
(07 Oct 01 | South Asia)
Timeline: Afghanistan air strikes
(07 Oct 01 | Americas)
Who is Osama Bin Laden?
(18 Sep 01 | South Asia)
What is terrorism?
(20 Sep 01 | Americas)
The trail to Bin Laden
(20 Sep 01 | Americas)
Analysis: Who are the Taleban?
(19 Sep 01 | South Asia)
Powell's challenge
(20 Sep 01 | Americas)
Military strikes: Key quotes
(07 Oct 01 | South Asia)
Profile: Mullah Mohammed Omar
(18 Sep 01 | South Asia)
Cheney: Power behind the throne
(20 Sep 01 | Americas)
Profile: Donald Rumsfeld
(20 Sep 01 | Americas)
The investigation and the evidence
(05 Oct 01 | Americas)
Guide to military strength
(25 Sep 01 | Americas)
Eyewitness: Effect of the attacks
(07 Oct 01 | South Asia)
Internet links:
The White House |
US Government |
Afghanistan Online |
The BBC is not responsible for the content of external internet sites