Ten species of Cephennomicrus are currently known to occur in Japan, predominantly in the Ryūkyū Archipelago. These extremely small beetles (adults of Japanese species do not exceed 1.2 mm) are rarely collected, and their true diversity may be in fact much greater. Two more species are described in the present study: C. aji sp. n. inhabiting Okinawa island, and C. ushimanus sp. n. found on Amami Ôshima island. Cephennomicrus aji has the smallest adults of all Japanese Scydmaeninae; the holotype male measures merely 0.66 mm of body length. The distribution of Japanese Cephennomicrus species is summarized, with the aedeagus of each species illustrated on the distribution map, to facilitate identifications and further study on this broadly distributed but poorly known cephenniine genus.