Nottebäcks nyklassicistiska kyrka är belägen intill landsvägen mellan Vetlanda och Sjösås. Kyrkan som är byggd i sten och in- och utvändigt putsad, uppfördes 1832-37 som gemensam kyrka för Nottebäcks och Granhults församlingar.
Kyrka ersatte en medeltida stenkyrka som var belägen söder om den nuvarande. Den gamla kyrkogården ingår idag som en del i den nya. I kyrkomiljön ingår även en kornbod i södra kyrkogårdsmuren, ditflyttad 1939 och en sockenstuga från 1862, som 1962 inrättades till församlingshem.
Den tidigare kyrkan låg söder om dagens kyrka och var betydligt mindre. Den var byggd i sten och lämningar efter den har påträffats vid gravgrävningar. Kyrkan saknade torn, men sydost om kyrkan låg en klockstapel som uppfördes på 1600-talet.