Early Cretaceous bryozoans are key to understanding the evolutionary radiation of order Cheilostomata, the dominant modern group. Prior to the current study, there were few records of any Cretaceous cheilostomes from eastern Asia, and no pre-Cenomanian records. We found bryozoan fossils to be common in brackish-water to marine deposits representing estuary-tidal-flat and shoreface-inner-shelf habitats in the late Albian-early Cenomanian Goshoura Group, Goshoura Island, Kyushu, Japan. Bryozoans from the Goshoura Group were poorly preserved; for identification, we made silicone casts of colony moulds and studied them by scanning electron microscopy (SEM). We detected six cheilostome and one cyclostome species (Berenicea sp. 1), all forming multiserial encrusting colonies.We erect the new genus Haplostoechios for two new Conopeum-like malacostegans (H. hayamiae and H. clusum), and describe another new malacostegan as Charixa goshouraensis. Additionally, we briefly describe three species detected from a single specimen each: the malacostegan Incertae sedis sp. 1 and neocheilostomes Incertae sedis sp. 2 and sp. 3. The Goshoura fauna is dominated by cheilostomes rather than cyclostomes, with malacostegans marginally outnumbering neocheilostomes. Bryozoans were a common component of the shell-rubble community, encrusting shells of one brachiopod and a broad variety of molluscan species, including 15 bivalves, two gastropods, an ammonite, a nautiloid and wood fragments containing Teredolites. Bryozoans were less diverse in estuary-tidal-flat deposits (three cheilostomes) than in shoreface-inner-shelf deposits (four cheilostomes and Berenicea sp. 1. Cheilostome average zooid length differed between the estuary-tidal-flat deposits (≤0.38 mm) and the shoreface-inner-shelf deposits (most specimens ≥0.49 mm). This study demonstrates that bryozoan assemblages worldwide were not of similar composition at the onset of cheilostome radiation, and underscores the need for further work in less studied regions.