Coiled nautiloids of the Tournaisian and early to middle Viséan (Early Carboniferous) have so far only become known from a few regions. Here we describe material from five localities in southern Algeria; these belong to four stratigraphic horizons (two horizons in the late Tournaisian, one horizon near the Tournaisian–Viséan boundary, one horizon in the early to middle Viséan). From these, the new genera Stroborineceras gen. nov. and Trilobitoceras gen. nov. and the following new species are described: Rineceras tenerum sp. nov., Stroborineceras insalahensis gen. et sp. nov., Stroborineceras felis gen. et sp. nov., Stroboceras mane sp. nov., Stroboceras ancilis sp. nov., Vestinautilus angulatus sp. nov., Vestinautilus papilio sp. nov., Vestinautilus inflexus sp. nov., Vestinautilus bicristatus sp. nov., Trilobitoceras peculiaris gen. et sp. nov., Aphelaeceras azzelmattiense sp. nov., Maccoyoceras saharensis sp. nov., Maccoyoceras habadraense sp. nov. and Maccoyoceras concavum sp. nov.