Unfortunately, you cannot create LeadHistory in test classes because the history object will not be inserted during test execution.
The only workaround you have is to use the @isTest annotation with (SeeAllData=true), which will expose the data in your org to the test class.
Please keep in mind that there is no guarantee that the LeadHistory objects are filled in the org you are running your test in, so please make sure your test code doesn't break if the data is not available.
Leadhistory lh = new Leadhistory(Field='<API namwe of field on history tracking is enabled>',LeadId=l.id);
insert lh;
http://www.salesforce.com/us/developer/docs/api/Content/sforce_api_objects_leadhistory.htm
But it is not working
Error-System.TypeException: DML operation INSERT not allowed on LeadHistory
Unfortunately, you cannot create LeadHistory in test classes because the history object will not be inserted during test execution.
The only workaround you have is to use the @isTest annotation with (SeeAllData=true), which will expose the data in your org to the test class.
Please keep in mind that there is no guarantee that the LeadHistory objects are filled in the org you are running your test in, so please make sure your test code doesn't break if the data is not available.
Hope this helps and good luck!
Regards,
Martijn Schwärzer