We applied an adaptive genetic algorithm (AGA) to search for low-energy crystal structures of Fe3S. A number of structures with energies lower than that of the experimentally reported Pnma and I-4 structures have been obtained from our AGA searches. These low-energy structures can be classified as layer-motif and column-motif structures. In the column-motif structures, Fe atoms self-assemble into rods with a bcc type of underlying lattice, which are separated by the holes terminated by S atoms. In the layer-motif structures, the bulk Fe is broken into slabs of several layers passivated by S atoms. Magnetic property calculations showed that the column-motif structures exhibit reasonably high uniaxial magnetic anisotropy. In addition, we examined the effect of Co doping to Fe3S and found that magnetic anisotropy can be enhanced through Co doping.