Fleischer nació en Trøndelag, y fue hijo de un pastor. Su padre murió cuando él era muy joven y se mudó con su madre a Trondheim, donde creció. Luego se inscribió en la Academia Militar de Noruega, donde se graduó en 1905, como el segundo mejor de su año.
Entre 1919 y 1923 sirvió como oficial en la 6.ª División, para luego convertirse en el oficial al mando del 14.º Regimiento de Infantería en Mosjøen, Nordland. Mientras estaba en Norland, Fleischer empezó a escribir manuales militares y desarrolló la teoría de las Fuerzas Defensivas Noruegas, tomando en cuenta las características especiales de su país.
El Mayor General Carl Gustav Fleischer obtendría el cargo de recapturar Narvik el 28 de mayo de 1940, coordinando las fuerzas británicas, francesas, polacas y noruegas, que debían desembarcar cerca y expulsar a las tropas del Mayor General Eduard Dietl, que se encontraba aislado y sin artillería en el pueblo (véase batallas de Narvik).
No obstante, el avance aliado fue demasiado cauteloso, y aunque para inicios de junio las tropas alemanas estaban acorraladas y la rendición era cuestión de tiempo, el panorama geopolítico cambió abruptamente cuando Francia fue conquistada por Alemania. Inmediatamente los británicos retiraron a todas las tropas aliadas (operación Alphabet), excepto a las noruegas. Los noruegos no pudieron mantener las posiciones ganadas por sí solos y el 9 de junio, el General Fleischer rindió sus tropas, al enterarse de que el Rey Haakon VII había escapado al Reino Unido con los principales miembros del gobierno el día anterior.
Tumba del General Fleischer.
El General Fleischer también se refugió en el Reino Unido, pero allí los roces que había mantenido con el gobierno noruego del laboristaJohan Nygaardsvold se reavivaron. En efecto, el General Fleischer había sido un opositor a la política pacifista y de neutralidad del gobierno noruego antes de la guerra, y ahora que se había demostrado que dicha política había sido errada, la enemistad entre los miembros del gobierno en el exilio y el general se intensificó. En efecto, a la hora de designar al nuevo Comandante en Jefe del Ejército Noruego, ya que el anterior comandante, el General Otto Ruge se había quedado en Noruega, no se consideró a Fleischer, quien le seguía en experiencia y en rango. En su lugar se seleccionó al MayorWilhelm von Tangen Hansteen quien fue promovido directamente a Teniente General.
A finales de 1940, el gobierno noruego le ordenó a Fleischer que se dirigiese a Canadá, a tomar el mando de las tropas noruegas estacionadas allí. A su llegada, Fleischer descubrió que en Toronto solamente operaba una base aérea, comandada por Ole Reistad, y que las fuerzas terrestres noruegas eran simbólicas.
El 1 de diciembre de 1942, el General Fleischer recibe el cargo de Militar Adjunto en Washington D. C. Este cargo era asignado a oficiales de menor rango, y el General Fleischer lo tomó como un insulto más del gobierno noruego. Molesto, el General Fleischer se disparó en el corazón el 19 de diciembre de 1942.
Sus cenizas fueron traídas de vuelta a Noruega al finalizar la guerra, pero el gobierno laborista de entonces se negó a realizar un funeral de estado. Aunque el Rey Haakon VII, y el futuro Olaf V asistieron, ningún representante del gobierno lo hizo. Eventualmente, un monumento en honor al general Fleischer se levantó en Harstad, pero aparte del Rey, ningún miembro del gobierno asistió a la ceremonia.