The agency issued a Red Notice, or internationally wanted persons alert, against Lewthwaite after the massacre at the Westgate Mall in Nairobi that claimed 72 lives including that of assailants.
Dubbed as the "white widow", the 29-year-old Muslim convert has been linked with Somali militant Islamist group Al-Shabab.
However, officials said she is wanted by Kenya on charges of being in possession of explosives and conspiracy to commit a crime dating back to December 2011.
She was married to 7/7 London suicide bomber Jermaine Lindsay. Lewthwaite's credit records show that she may have lived in South Africa.
Circulated to all 190 Interpol member countries, the Red Notice represents one of the agency's most powerful tools in tracking international fugitives.
Lewthwaite - who uses the alias "Natalie Webb" - had previously only been wanted at national level for the possession of a fake South African passport.
--IANS (Posted on 27-09-2013)