Kastlösa kyrka är belägen på östra landborgen invid västra landsvägen i norra delen av Kastlösa by. Omedelbart väster om kyrkogården ligger Kastlösa stiftsgård. När man på 1850-talet uppförde den nya kyrkan lät man bygga en ny prästgård och den gamla flyttades till andra sidan vägen och blev Kastlösas första skola. Kyrkan Omkring 1850 blev Kastlösas lilla klövsadelkyrka från 1100-talet för liten. Den hade bestått av långhus, kor och östtorn och ett västtorn från 1200-talet. Kastlösa nya kyrka uppfördes efter ritningar av Adolf Johan Hawerman år 1855. Byggmästare var Peter Isberg från Glömminge.

I sockenstämmoprotokoll sägs att kyrkan uppfördes ”jämförelsevis billigt tack vare att det mesta av arbetet och körningen utfördes av församlingsborna själva”. Den kom att uppföras norr om den gamla kyrkan. Den nya kyrkan består av rektangulärt kyrkorum, indelat i tre skepp, med kor i öster, sakristia i norr och torn i väster. De vitputsade murarna täcks av sadeltak, tornet kröns av en lanternin med en kort spira. Närmare hundra år efter kyrkans invigning gjordes stora invändiga renoveringar inför jubileet. Kyrkorummet omformades på ett enhetligt sätt och kyrkorummet täcktes bland annat av ett plant innertak. Bänkinredningen, läktaren och predikstolen är från samma tillfälle.