Pakistani officials say the Taliban commander known as Fazlullah has been orchestrating raids on Pakistani security forces from Afghanistan, where he fled several years ago after a Pakistani army offensive against his stronghold in the Swat Valley.
Pakistan has repeatedly called on Afghanistan to hunt down Fazlullah, whose fighters cross the border in their hundreds, set up ambushes and attack army checkpoints.
"If somebody is living in somebody's house and you ask him 'who is giving you food, who is giving you all this shelter?' You know he is in Afghanistan," Rehman Malik told Reuters in a weekend interview.
"I think some of the elements (of the Afghan government) there are supporters. Maybe state actors, maybe non-state actors."
Malik provided no evidence to support his assertion that elements within Afghanistan were supporting Fazlullah, nor did he give further details.
"These comments made by the Pakistani Interior Minister are irresponsible and a baseless allegation," said Afghan Interior Ministry spokesman Sediq Sediqqi.
"Afghanistan has been under attacks from safe havens of insurgents inside Pakistan, and we are quite sure that Mullah Fazlullah is somewhere in Pakistan."
Fazlullah and other militant leaders based along the frontier complicate U.S. efforts to stabilise the region before most NATO combat troops withdraw from Afghanistan by the end of 2014.
The issue has strained ties between Islamabad and Kabul.
Afghanistan has long accused Pakistan of backing militants said to be based on its soil who cross the border to attack Afghan and NATO forces, including the Haqqani network, blamed for a series of high-profile attacks on Kabul.
Islamabad denies the allegations.
Afghan President Hamid Karzai said on Sunday he accepted parliament's decision to dismiss the country's two top security ministers for failing to stop cross-border shelling blamed on Pakistan, in what could be a blow to NATO plans to hand over security responsibilities to Afghan forces.
The fractious parliament voted on Saturday to remove Defence Minister Abdul Rahim Wardak and Interior Minister Bismillah Mohammadi over a series of recent insurgent assassinations of top officials, as well as the cross-border fire incidents that infuriate many Afghan voters as well as politicians.
Afghanistan has rushed additional troops and artillery to the mountainous border with Pakistan.
Pakistan's military has said it only responds to attacks by militants, including Pakistan Taliban operating from what it says are havens in Afghan territory.
In his heyday, Fazlullah was known as "FM Mullah", for his fiery radio speeches broadcast in Swat, which was a tourist resort before he and his men imposed a reign of terror there.
A burly man in his thirties with a heavy black beard, Fazlullah dispatched his men to publicly flog and behead opponents, or anyone they deemed immoral.
Fazlullah has re-emerged as a major security headache for the Pakistani military, which is already stretched fighting other Taliban insurgent leaders.