Steenstrup utgav vetenskapliga arbeten inom zoologi, botanik, arkeologi och geologi. Av sina studier av danska mossar kunde han dra slutsatser om invandringen av träd och djur i Danmark efter istiden. Steenstrup var även en av de första som fastslog förekomsten av förhistoriska boplatsavlagringar i Danmark, så kallade kökkenmöddingar. Far till Johannes Steenstrup och farbror