Eyewitnesses said the militants shot in the air to warn people away as they began smashing the shrines.
Timbuktu is a World Heritage site, with centuries-old shrines to Islamic saints, revered by Sufi Muslims.
The al-Qaeda-linked Ansar Dine group that seized the city in April says they are idolatrous and wants them removed.
The UN Security Council condemned the destruction last week of some shrines, warning it could constitute a war crime.
This means that a case could be referred to the International Criminal Court (ICC) in The Hague, whose prosecutor has already condemned the recent destruction of Muslim tombs.
About a dozen militants drove up to the 14th-Century Djingareyber mosque in an armoured four-wheeled truck, armed with guns, pickaxes and hoes, one Timbuktu resident who witnessed the scene told Reuters news agency.
Other residents described how the fighters blocked the two main roads leading to the mosque and shot in the air to scare people off.
"The two tombs are adjacent to the western wall of the great mosque and the Islamists have hoes [and] chisels - they are hitting the mausoleums which are made out of packed earth," another witness told the AFP news agency.
The UN cultural agency Unesco and Mali's government have already called on Ansar Dine to halt its campaign.
The group has destroyed several of 16 listed mausoleums in the city, and has vowed to smash them all.
Its fighters have also broken down the sacred door of the 15th-Century Sidi Yahia mosque.
Unesco has also expressed concern that valuable artefacts and manuscripts may be smuggled out of the region and has urged neighbouring countries to prevent this.
Timbuktu owes its international fame to its role as a centre of Islamic learning, based in its three large mosques, in the 15th and 16th Centuries. It is also known as the "city of 333 saints", which originate in the Sufi tradition of Islam.
Ansar Dine's Salafist beliefs condemn the veneration of saints.
The group seized control of Timbuktu in April, after a coup left Mali's army in disarray.
Initially, it was working with secular ethnic Tuareg rebels demanding independence for northern Mali's desert territories but the groups have recently clashed and Islamist forces are in control of northern Mali's three main centres - Timbuktu, Gao and Kidal.
2012. "Tombs in Timbuktu's Djingareyber mosque 'destroyed'". BBC News. Posted: Available online: http://www.bbc.co.uk/news/world-africa-18785895