Er wurde am 21. Februar 1801 in Bad Schandau (damals Schandau) geboren, besuchte das Gymnasium in Bautzen.
1818 kam er an die Universität Leipzig zum Studium der Theologie und der orientalischen Philologie. Außerdem betrieb er bei Sylvestre de Sacy in Paris Sprachstudien in Hebräisch, Syrisch, Samaritisch, Äthiopisch und Koptisch.

Nach Anstellungen an der Dresdner Kreuzschule und einer Professur für persische Sprache an der Universität Petersburg erhielt er 1835 einen Ruf nach Leipzig und übernahm im Frühjahr 1836 als Nachfolger des Theologen Ernst Karl Rosenmüller den Lehrstuhl für Morgenländische Sprachen. Der Lehrstuhl gehörte zunächst zur Theologischen Fakultät, ab 1840 zur Philosophischen Fakultät.

Fleischer setzte die Traditionslinie der Arabistik in Leipzig fort, die 1724 mit Johann Christian Clodius (1676 bis 1745) und danach Johann Jacob Reiske (1716 bis 1774) begonnen hatte. Heinrich Leberecht Fleischer aber führte die Leipziger Arabistik zu einem weltweit beachteten Ansehen. Er machte die Universität zu einem europäischen Zentrum der Lehre und Forschung der mohammedanischen Kultur. Die Leipziger Universität wurde zum "Mekka der Arabistik".
Fleischer widmete sich vorzugsweise der Einführung ins Arabische, auch ins Persische und Türkische. Er hatte Schüler aus Deutschland und vielen Ländern der Welt, z.B. England, Österreich, den Niederlanden, dem Orient und Amerika, von denen später viele Gelehrte und Beamte in diplomatischen Diensten wurden. Von seinen Schülern wurde Fleischer der "Scheich" genannt.

Ab 1853 wurden mit maßgeblicher Unterstützung Fleischers die insgesamt 487 Bände umfassenden sogenannten Refaiya-Handschriften für die Universitätsbibliothek Leipzig angekauft, wodurch die Bibliothek in die Reihe der europäischen Bibliotheken mit einer signifikanten Anzahl bedeutungsvoller orientalischer Handschriften aufrückte.

Im September 1843 wurde in der Wohnung Heinrich Leberecht Fleischers in der Nikolaistraße der Beschluß zur Schaffung einer Vereinigung von Orientalisten gefaßt. Am 2. Oktober 1845 wurde dann nach dem Vorbild der Societe asiatique in Paris die "Deutsche Morgenländische Gesellschaft" mit Sitz in Leipzig gegründet, zu deren Mitbegründern Heinrich Leberecht Fleischer und der Indologe Hermann Brockhaus gehörten. Den Tätigkeitsbereich ihrer Mitglieder bilden die Sprachen und Kulturen des Orients, Asiens, Ozeaniens und Afrikas sowie die Beziehungen dieser Gebiete untereinander und zu den Nachbarregionen.

Mit Fleischers Tod am 10. Februar 1888 ging die ruhmreichste Periode der Leipziger Arabistik zu Ende.