--- a/src/plugins/filecheck/CMakeLists.txt
+++ b/src/plugins/filecheck/CMakeLists.txt
@@ -1,20 +1,46 @@
 include (LibAddMacros)
-if (DEPENDENCY_PHASE)
-	find_package (Iconv QUIET)
-
-	if (NOT Iconv_FOUND)
-		remove_plugin (filecheck "Cannot find iconv library")
-	endif ()
+find_package (Iconv QUIET)
 
+if (DEPENDENCY_PHASE)
 	if (ENABLE_ASAN AND CMAKE_SYSTEM_NAME MATCHES FreeBSD)
 		# See also: https://cirrus-ci.com/task/5751822404288512?command=tests#L237-L239
 		remove_plugin (filecheck "the unit test of the plugin fails on FreeBSD if ASan is active")
 	endif (ENABLE_ASAN AND CMAKE_SYSTEM_NAME MATCHES FreeBSD)
 endif ()
 
-add_plugin (
-	filecheck
-	SOURCES filecheck.h filecheck.c
-	INCLUDE_DIRECTORIES ${Iconv_INCLUDE_DIRS}
-	LINK_LIBRARIES ${Iconv_LIBRARIES}
-	ADD_TEST INSTALL_TEST_DATA COMPONENT libelektra${SO_VERSION}-extra)
+if(Iconv_FOUND)
+	add_plugin (
+		filecheck
+		SOURCES filecheck.h filecheck.c
+		INCLUDE_DIRECTORIES ${Iconv_INCLUDE_DIRS}
+		LINK_LIBRARIES ${Iconv_LIBRARIES}
+		ADD_TEST INSTALL_TEST_DATA COMPONENT libelektra${SO_VERSION}-extra)
+else()
+	# Sometime the build environment is not setup
+	# in a way CMake can find Iconv on its own by default.
+	# But if we simply link against iconv (-liconv), the build may succeed
+	# due to other compiler/link flags.
+	set(CMAKE_REQUIRED_LIBRARIES "iconv")
+	check_c_source_compiles("
+		#include <stddef.h>
+		#include <iconv.h>
+		int main() {
+			char *a, *b;
+			size_t i, j;
+			iconv_t ic;
+			ic = iconv_open(\"to\", \"from\");
+			iconv(ic, &a, &i, &b, &j);
+			iconv_close(ic);
+		}
+		"
+	Iconv_EXPLICITLY_AT_ENV)
+	if(Iconv_EXPLICITLY_AT_ENV)
+		add_plugin (
+			filecheck
+			SOURCES filecheck.h filecheck.c
+			LINK_LIBRARIES iconv
+			ADD_TEST INSTALL_TEST_DATA COMPONENT libelektra${SO_VERSION}-extra)
+	else()
+			message(FATAL_ERROR "Cannot find iconv library")
+	endif()
+endif()
--- a/src/plugins/iconv/CMakeLists.txt
+++ b/src/plugins/iconv/CMakeLists.txt
@@ -1,19 +1,45 @@
-if (DEPENDENCY_PHASE)
-	find_package (Iconv QUIET)
+find_package (Iconv QUIET)
 
+if (DEPENDENCY_PHASE)
 	if (ENABLE_ASAN AND CMAKE_SYSTEM_NAME MATCHES FreeBSD)
 		# See also: https://cirrus-ci.com/task/5751822404288512?command=tests#L253-L255
 		remove_plugin (iconv "the unit test of the plugin fails on FreeBSD if ASan is active")
 	endif (ENABLE_ASAN AND CMAKE_SYSTEM_NAME MATCHES FreeBSD)
-
-	if (NOT Iconv_FOUND)
-		remove_plugin (iconv "Cannot find iconv library")
-	endif ()
 endif ()
 
-add_plugin (
-	iconv
-	SOURCES conv.h iconv.c
-	INCLUDE_DIRECTORIES ${Iconv_INCLUDE_DIRS}
-	LINK_LIBRARIES ${Iconv_LIBRARIES}
-	ADD_TEST TEST_README COMPONENT libelektra${SO_VERSION}-extra)
+if(Iconv_FOUND)
+	add_plugin (
+		iconv
+		SOURCES conv.h iconv.c
+		INCLUDE_DIRECTORIES ${Iconv_INCLUDE_DIRS}
+		LINK_LIBRARIES ${Iconv_LIBRARIES}
+		ADD_TEST TEST_README COMPONENT libelektra${SO_VERSION}-extra)
+else()
+	# Sometime the build environment is not setup
+	# in a way CMake can find Iconv on its own by default.
+	# But if we simply link against iconv (-liconv), the build may succeed
+	# due to other compiler/link flags.
+	set(CMAKE_REQUIRED_LIBRARIES "iconv")
+	check_c_source_compiles("
+		#include <stddef.h>
+		#include <iconv.h>
+		int main() {
+			char *a, *b;
+			size_t i, j;
+			iconv_t ic;
+			ic = iconv_open(\"to\", \"from\");
+			iconv(ic, &a, &i, &b, &j);
+			iconv_close(ic);
+		}
+		"
+	Iconv_EXPLICITLY_AT_ENV)
+	if(Iconv_EXPLICITLY_AT_ENV)
+		add_plugin (
+			iconv
+			SOURCES conv.h iconv.c
+			LINK_LIBRARIES iconv
+			ADD_TEST TEST_README COMPONENT libelektra${SO_VERSION}-extra)
+	else()
+		message(FATAL_ERROR "Cannot find iconv library")
+	endif()
+endif()
