Martin Fleckenstein studierte Geologie und Paläontologie an der Technischen Hochschule Darmstadt (heute TU Darmstadt) bis zum Vordiplom. 1978 wechselte er als Fulbright-Stipendiat zur Colorado School of Mines in Golden (Colorado, USA), wo er eine Masterarbeit zur präkambrischen Geologie in der zentralen Laramie Range in Wyoming anfertigte. Von 1980 bis 1982 war er als Hochschulassistent am Mineralogisch-Petrographischen Institut der Universität Köln tätig. Hier promovierte er 1982 mit einer Arbeit zur "Deformation und Metamorphose in der alpinen Subduktionszone südlich des Monte-Rosa-Massivs, Norditalien".

Nach seiner Promotion war Martin Fleckenstein bei der BEB Hannover tätig, wo er bald leitende Positionen übernahm. Sein beruflicher Werdegang beinhaltete Aufenthalte beim BEB-Anteilseigner Exxon in New Orleans und bei ExxonMobil in Houston, USA. 2005 wurde er zum Chefgeologen der Wintershall Holding GmbH in Kassel berufen, und von 2007 bis 2009 war er als Managing Director von Wintershall Russland in Moskau beschäftigt. Von 2009 bis zu seiner Pensionierung war er Director of Exploration von Wintershall, seitdem ist er beratend sowie als Mitglied im Aufsichtsrat der VNG tätig.

2013 konnte Martin Fleckenstein für die regelmäßig stattfindende Lehrveranstaltung "Angewandte Erdölgeologie" gewonnen werden. Diese führte bald zu einem großen Interesse der Studierenden an diesem Fach, auch weil die Lehre durch einen Praktiker aus dem Berufsleben eine Besonderheit darstellt. Es ist ein Glücksfall für unseren Fachbereich, dass dieses hochattraktive Fach von einem international exzellent ausgewiesenen Erdölgeologen vertreten wird.