We performed adaptive genetic algorithm (AGA) search for low-energy atomic structures of the rare earth free permanent magnet material Fe3S. A number of structures with energy lower than that of the experimentally reported Pnma structure have been obtained from our AGA search as shown in the figure. These low-energy structures can be classified as layer motif structures and column motif structures.  In the column motif structures, Fe atoms are self-assemble into bcc-like rods separated by the holes formed by S atoms as shown in figure (b). In the layer motif structure, the bulk bcc Fe is braked into slabs of several layers of thickness by S atoms as shown in figure (c). Magnetic calculations showed that the column motif structures exhibit reasonably high uniaxial magnetic anisotropy. In addition, we also found Co doping could enhance the magnetic anisotropy of Fe3S.