Kyrkan är byggd ca 1788-1791 i gustaviansk stil, delvis på initiativ från den dynamiske riksdagsmannen för bondeståndet, Knuth Persson (Hörby) kallad ”Mjällby kung”. Den nuvarande kyrkan ersatte då en romansk 1100-talskyrka av sten och tegel (med två torn), vilken i sin tur lär ha ersatt en träkyrka ifrån missionstiden, vilken i sin tur lär ha rests på en hednisk offerplats. Under flera epoker under medeltiden hade bl.a. ärkebiskopen i Lund ekonomiska intressen i Mjällby by.
Den nuvarande kyrkan hyser flera vackra och intressanta historiska föremål ifrån bl.a. renässansen. Altaruppsatsen från AD 1621 är donerad till kyrkan av "Skåne-kungen" Tage Thott, dansk länsherre på Sölvesborgs slott.