Multicellularity is key to the functional and ecological success of the Eukarya, underpinning much of their modern diversity in both terrestrial and marine ecosystems. Despite the widespread occurrence of simple multicellular organisms among eukaryotes, when this innovation arose remains an open question. Here, we report cellularly preserved multicellular microfossils (Qingshania magnifica) from the similar to 1635-million-year-old Chuanlinggou Formation, North China. The fossils consist of large uniseriate, unbranched filaments with cell diameters up to 190 micrometers; spheroidal structures, possibly spores, occur within some cells. In combination with spectroscopic characteristics, the large size and morphological complexity of these fossils support their interpretation as eukaryotes, likely photosynthetic, based on comparisons with extant organisms. The occurrence of multicellular eukaryotes in Paleoproterozoic rocks not much younger than those containing the oldest unambiguous evidence of eukaryotes as a whole supports the hypothesis that simple multicellularity arose early in eukaryotic history, as much as a billion years before complex multicellular organisms diversified in the oceans.