Security officials, speaking on condition of anonymity, told the Associated Press that 10 soldiers and eight civilians died in the explosion, although media reports varied on the number of people killed in the blast.
The attack marks the deadliest strike on the military since its battle with an Islamic militant group in the country's north a year ago. Lebanese officials described it as a "terrorist attack targeting the army directly," according to the AP.
Lebanese President Michel Suleiman release a statement saying: "The army and security forces will not yield to attempts to terrorize them with attacks and crimes."
The bomb, which was placed in a bag next to the bus, was detonated by remote control, security officials told news agencies. The small public bus was carrying passengers from the northern Akkar region, home to many military members.
Electrician Hatem Hussein, 24, said he ran to the scene after hearing the blast. "The wounded were lying on the ground, men in military uniforms," he told the AP.
Suspicion was quickly directed at Fatah al Islam, a Sunni militant group inspired by al-Qaida, for carrying out the attack in a bid to seek revenge on the Lebanese army for earlier clashes. There was no immediate claim of responsibility for the bombing.
Last year, the Lebanese army -- led by Suleiman before he was elected president in May -- carried out a high-profile, four-month battle with the group in the Nahr al Bared Palestinian refugee camp near Tripoli. Around 170 soldiers were killed during the fighting, which ended with the Fatah al Islam group fleeing from the camp.
Fatah al Islam claimed responsibility for a May 31 bomb attack that killed one soldier, and is suspected to be involved in Wednesday's blast.
The group's leader Shaker al-Absi said they would, "hunt down the followers of Gen. Michel Suleiman."
Ongoing sectarian fighting between Tripoli's Sunnis and Alawites, who are Shiites, have left at least 22 dead in recent months.
Suleiman was scheduled to visit with Syrian President Bashar al-Assad later Wednesday in the first visit there by a Lebanese president since 2005 -- a meeting intended to help mend troubled ties between the neighboring countries. Syria maintained a military presence in Lebanon for 29 years until international pressure forced Syrian troops to withdraw following the assassination of former Lebanese Prime Minister Rafik Hariri in 2005.
Some media reports questioned whether the bombing was meant to undermine the visit.
"The investigation has begun and there are many interpretations, political interpretations," said Information Minister Tareq Mitri.
Syria's Foreign Ministry denounced the explosion and voiced support for Lebanon "against the hands that try to disrupt its security and stability," the AP reported.
On Tuesday, parliament gave a vote of confidence to Lebanon's national unity government after months of negotiations between Prime Minister Fuad Saniora, supported by the West, and Hezbollah, a group backed by Iran and Syria.
Saniora said the attack would not stop the new government from forming.