Si el historial lo guarda firefox en una carpeta en disco duro, puedes usar algún programa como recuva:
http://www.piriform.com/recuva
Es gratuito y tiene varias opciones para recuperar datos borrados accidentalmente.
También busca en tu papelera (en el caso de windows) y trata de ubicar la carpeta de historial.
Ahora que si la nueva instalación de firefox escribió una nueva carpeta de historial donde estaba la antigua, puede que ya no recuperes eso.
Espero haber ayudado.
Saludos :)