Er wurde 1842 als Sohn des Pächters Johan Peter Steenstrup (1814–1849) und dessen Ehefrau Sinned Claudine Lund (1803–1863) geboren. Sein Onkel war der Zoologe Japetus Steenstrup. Steenstrup ging in Thisted zur Schule und legte 1863 eine Prüfung in Pharmazie ab. Sein Studium zum magister artium beendete er jedoch nicht. 1866 wurde er Assistent am Geologischen Museum in Kopenhagen. Dort blieb er bis 1889, als er Geologe (später Staatsgeologe) an der Dänischen Geologischen Forschungsanstalt wurde. 1897 wurde er jedoch entlassen und fand keine Anstellung mehr. Finanziell unabhängig setzte er seine Arbeiten am Geologischen Museum fort, wo ihm bis zu seinem Tod ein Raum zur Verfügung stand.
Als Mitglied einer schwedischen Expedition, die das Ziel hatte, gediegeneEisenblöcke zu bergen, die Adolf Erik Nordenskiöld auf der Diskoinsel gefunden hatte, kam er 1871 erstmals nach Grönland. Schon im darauffolgenden Jahr kehrte er in dasselbe Gebiet zurück. Ihm gelang der Nachweis, dass es sich bei diesen in Basalt eingebetteten Blöcken nicht – wie zunächst vermutet – um Meteoriten handelte. Steenstrup unternahm bis 1899 insgesamt neun Reisen nach Grönland. Die längste dauerte zweieinhalb Jahre. Seine Studien trugen wesentlich zur Lösung der alten umstrittenen Frage nach der Lage der Ostsiedlung der Grænlendingar bei. Er sammelte auch Pflanzenfossilien unter anderem aus dem Miozän von Nordwestgrönland, die von Oswald Heer (Flora fossilis arctica) bearbeitet wurden. Ein Großteil seiner grönländischen Sammlung ging bei einem Brand in Schloss Christiansborg 1884 verloren. Wichtig für Dänemarks Geologie waren seine Studien zur Dünenwanderung auf Jütland.
Om de Nordenskiöldske Jærnmasser og om Forekomsten af gedigent Jærn i Basalt. In: Videnskabelige meddelelser fra den Naturhistoriske forening i Kjøbenhavn. Band 38, 1876, S. 284–306 (Digitalisat, dänisch)
Ueber die Lagerungsverhältnisse der Kohlen und Versteinerungen führenden Bildungen auf der Westküste von Grönland. In: Oswald Heer: Flora fossilis arctica. Die fossile Flora der Polarländer. Siebenter Band, J. Wurster & Comp., Zürich 1883, S. 228–250 (e-rara); Karte: Die kohlenführenden Ablagerungen an der Westküste von Grönland (e-rara)
