His ancestors had migrated from Elbing in East Prussia to Norway, first with Tobias Fleischer (1630–1690) who found a position in Kongsberg. The current lineage is descended from Tobias' nephew Herman Reinhold Fleischer (1656–1712), who also had notable children in Denmark. Carl Gustav Fleischer was a descendant of Herman's son Philip Johan Fleischer (1699–1763). Notable relatives include Philip's brother Baltzer Fleischer and grandnephew Palle Rømer Fleischer, and Carl Gustav's brother, bishop Andreas Fleischer. Carl Gustav Fleischer was also a more distant relative of Carl August Fleischer, Nanna Fleischer, Agnes Fleischer and August Fleischer.