Fjelsted kirke ligger malerisk på en stor grusbanke i udkanten af den store kirkegård midt i den gamle landsby. Der har den ligget i ca 800 år. I middelalderen var kirken viet Skt. Laurentius

 

Kirkens kor og skib er opført i romansk stil på profileret dobbeltsokkel. Et originalt tilmuret romansk vindue kan spores i korets nordvæg. I korets østvæg er der to gemmenicher.

 

Oprindelig havde kirken bjælkeloft, men i senmiddelaldren byggede man hvælvinger i både kor og skib, og korbuen blev udvidet. Desuden blev der opført våbenhus ved syddøren, hvor mandsdøren tidligere havde været.

 

Senmiddelalderen var en rig tid for kirken. Lige før reformationen, i 1523, fik den katolske kirke store private donationer, ofte i forbindelse med dødsmesser. Dette gav kirken mulighed at gennemføre omfattende forandringer efter tidens gotiske stil.

 

I 1872 blev kirken udvidet med sideskibet mod nord, da man på daværende tidspunkt manglede siddepladser, og i 1937 blev kapellet bygget