År 1767 stod den nya kyrkan i Algutsboda klar. Kvar från den gamla kyrkan fanns sakristian i sten. Denna hade byggts till mot söder och försetts med ytterligare ett fönster i norr. Det nya långhuset och tornet byggdes i sten och försågs med tak av spån. En märklig detalj när det gäller långhuset är de avvikande måtten. Den norra långhusväggen är 120 cm längre än den södra, en skillnad som är märkbar i kyrkorummet. Varför det är så här vet ingen. Man har spekulerat om att det är ett rent misstag. En annan teori är att det skulle vara mycket medvetet gjort för att minna om alltings ofullkomlighet. Inte ens Herrens hus är perfekt. Kyrkan är traditionellt orienterad med torn i väster, kor i öster och sakristia i norr.
Algutsboda kyrka har såväl interiört som exteriört genomgått flera stora förändringar som omgestaltat den ursprungliga byggnaden. Spåren av 1700-talets kyrka finns dock fortfarande. Mitten av 1700-talet var när det gäller konst och arkitektur en brytningstid mellan den gamla barocken och den nya klassicismen. Den senare skulle från slutet av 1800-talet bli den viktigaste inspirationskällan för de kyrkor som byggdes. Exempel på kyrkor i Algutsbodas närhet som byggdes vid samma tid är Madesjö och Vissefjärda kyrkor. Till skillnad från dessa båda kyrkor byggdes Algutsboda kyrka från början med ett torn medan Madesjö kyrka försågs med ett torn under 1830-talet medan Vissfjärda kyrka än idag saknar torn.
Ett av de tydliga 1700-tals dragen i Algutsboda kyrka är kyrkobyggnadens form. Långhuset är brett och lite satt till karaktären till skillnad från de långhus som byggdes 50-70 år senare i nyklassicistisk stil. Trots att takfoten höjdes med två fot i slutet av 1800-talet har byggnaden kvar detta drag. Även om taket minskades i och med höjningen av väggarna är takytorna stora. Taket är än idag klätt med spån vilket är ett viktigt karaktärsdrag för Algutsboda kyrka. I en trakt som låg långt från tegelbruk var spån det biligaste taktäckningsmaterialet och också lättast att anskaffa. Ett annat typiskt drag är det rakavslutade koret. Även Vissefjärda kyrka har detta drag. Madesjö kyrka hade ursprungligen ett rakavslutat kor men försågs på 1880-talet med en absid.
Den ursprungliga kyrkan hade stickbågiga fönster och dörröppningar samt ett torn med lanternin som började i höjd med långhusets taknock. I väster fanns en ingång och i söder två. Långhuset hade fyra parställda fönster och i varje gavel fanns ytterligare två fönster. Från 1891 finns ett ritningsförslag hur man tänkte sig att det nya tornet skulle se ut. Ritningen är signerad av en man vid namn F K Ekberg. Detta förslag verkar ha genomförts i det närmaste fullt ut. Ritningen verkar avbilda kyrkans långhus som det såg ut vid den här tiden och inte omfatta några förändringar i denna del av byggnaden. Ritningen visar att även den västra ingången till kyrkan ursprungligen har varit stickbågig. I långhusets västra gavel fanns dels ett högt stickbågigt fönster, dels ett fönster med samma utformning men halva höjden. Det har inte gått att återfinna i källmaterialet när de stickbågiga fönstren ändrades till rundbågiga men troligen var det i samband med den stora ombyggnaden i slutet av 1800-talet. Dels pågick stora arbeten med kyrkan, dels ligger förändringarna stilmässigt rätt i tiden. Också ingången i väster blev troligen rundbågig vid den här tiden.
En viss osäkerhet har rått kring om höjningen av väggarna verkligen gjordes men i samband med lagning av putsen under 1990-talet då stora delar av pusten på den östra gaveln och långhusets sydöstra hörn var nedknackad kunde man tydligt se att väggarna hade byggts på. Höjningen av väggen var en del av de stora förändringar som genomfördes vid ombyggnaden på 1890-talet. Vid denna renovering revs även spåntaket revs ner för att läggas om och det ledde till den olycka som i Algutsboda går under benämningen spantraset. Eftersom tornet skulle byggas om hade två av spanten närmast tornet tagits ner. Det gjorde att övriga spant saknade stöd och i början av juni 1892 rasade samtliga spant ner. Flera inventarier skadades vilket redogörs närmare för närmare under rubriken interiör. Renoveringen av kyrkan blev genom olyckan betydligt mera omfattande än vad som från början varit planerat.
Under 1900-talet är det framförallt två förändringar som påverkar kyrkans exteriör. Vid renoveringen 1934-36 sattes den västra av de båda ingångarna i söder igen och den östra ska ha förminskats. I samband med renoveringen 1990-95 handikappanpassades ingången i väster med en ramp i granit. I övrigt har ett normalt underhåll i form av putslagningar, lagning av spåntaket samt underhåll av fönster, dörrar och andra detaljer har genomförts. Vid lagning av putsskador som utfördes 1997 gjordes en underökning av de underliggande putslagren. Det visade sig då att kyrkan ursprungligen varit avfärgad i rosa. Därefter, möjligen från 1890-talet, var kyrkan tegelröd. Någon gång under 1900-talets första hälft blev kyrkan svagt gul och slutligen vit.
Idag präglas Algutsboda kyrka främst av den stora ombyggnaden i slutet av 1800-talet som försåg kyrkan med dess spetsiga torn, förhöjda väggliv och rundbågiga fönster.
Interiör