Steenstrup blev juris kandidat 1869 och juris doktor 1882 samt var 1882-1917 professor i historia vid Köpenhamns universitet. Han ägnade sig särskilt åt den äldre medeltiden och danska folkets inre utveckling. Han utgav Studier over kong Valdemars jordebog (1873, med upplysningar om landets förvaltning på 1200-talet), det omfattande verket Normannerne (fyra band, 1873-82), Den danske bonde og friheden (1888; tredje upplagan 1912), Historieskrivningen i Danmark i det 19. aarhundredet (1889) och Vore folkeviser fra middelalderen (1891) samt skildrade forntiden och den äldre medeltiden (till 1241) i "Danmarks riges historie" (I, 1904).
Steenstrup författade även en serie viktiga uppsatser, angående Danmarks inre förhållanden, i "Historisk tidsskrift", däribland Vornedskabet hos den danske bonde, Fæstebondens retsforhold i ældre tid, Nogle undersøgelser om guders navne i de nordiske stedsnavne, Nogle bidrag til vore landsbyers og bebyggelsens historie, vidare Danmarks sydgrænse og herredømmet över Holsten 800-1100 (1900) och Venderne og de danske før Valdemar den stores tid (1900). Några spridda uppsatser samlade han i Fra fortid og nutid (1892), varjämte han utgav översikten Etnografien (1902), Navnebog (1902; andra upplagan 1903, jämte V. Dahlerup), De danske stednavne (1908), Indledende studier over de ældste danske stednavnes bygning (1909) och Statsrettens udvikling gjennem tiderne og nutidens statsforfatninger (1916), Den danske kvindes historie (två band, 1917), Mænds og kvinders navne i Danmark gennem tiderne (1918), Historieskrivningen i det 19. aarhundredet (1921) samt två arbeten om J.C. Jacobsen och hans son Carl.