The origin and early diversification of decapod crustaceans and their expansion from marine to continental environments are key events in arthropod evolution. Rare fossil decapods are known from the Palaeozoic, and the earliest eumalacostracans with undoubted decapod affinities are the Late Devonian Palaeopalaemon and Aciculopoda, found in offshore marine deposits. Here, we describe a new species of the shrimp Tealliocaris found in floodplain and temporary pond deposits from the Famennian (Late Devonian) of Belgium, together with a rare Palaeozoic assemblage of other crustaceans (conchostracans, notostracans and anostracans) and chelicerates (eurypterids). Tealliocaris walloniensis sp. nov. documents the earliest occurrence of continental decapod crustaceans and indicates that decapods have been part of continental ecosystems at least since the Late Devonian.