Four species of Arthothelium from Africa and Socotra are described as new to science: Arthothelium atrorubrum from Madagascar, characterized by irregularly rounded blackish ascomata with a deeply red hypothecium and submuriform ascospores; Arthothelium aurantiacopruinosum from the Democratic Republic of the Congo, characterized by black, irregularly rounded to stellate, orange pruinose ascomata and muriform ascospores with two larger terminal cells; Arthothelium frischianum from Madagascar, characterized by brownish-black minute irregular ascomata with remnants of thallus and muriform ascospores with one larger terminal cell; Arthothelium miesii from Socotra (Yemen), characterized by a thick thallus, immersed, stellate to cerebriform, brownish, greyish pruinose ascomata and submuriform ascospores. A key to all reported species of Arthothelium from tropical Africa (South Africa excluded) and Socotra is provided.