diff --git a/clang-tools-extra/clang-tidy/bugprone/FoldInitTypeCheck.cpp b/clang-tools-extra/clang-tidy/bugprone/FoldInitTypeCheck.cpp
--- a/clang-tools-extra/clang-tidy/bugprone/FoldInitTypeCheck.cpp
+++ b/clang-tools-extra/clang-tidy/bugprone/FoldInitTypeCheck.cpp
@@ -24,9 +24,24 @@
     return anyOf(
         // Pointer types.
         pointsTo(BuiltinTypeWithId(ID)),
-        // Iterator types.
-        recordType(hasDeclaration(has(typedefNameDecl(
-            hasName("value_type"), hasType(BuiltinTypeWithId(ID)))))));
+        // Iterator types have an `operator*` whose return type is the type we
+        // care about.
+        // Notes:
+        //   - `operator*` can be in one of the bases of the iterator class.
+        //   - this does not handle cases when the `operator*` is defined
+        //     outside the iterator class.
+        recordType(
+            hasDeclaration(cxxRecordDecl(isSameOrDerivedFrom(has(functionDecl(
+                hasOverloadedOperatorName("*"),
+                returns(qualType(hasCanonicalType(anyOf(
+                    // `value_type& operator*();`
+                    references(BuiltinTypeWithId(ID)),
+                    // `value_type operator*();`
+                    BuiltinTypeWithId(ID),
+                    // `auto operator*();`, `decltype(auto) operator*();`
+                    autoType(hasDeducedType(BuiltinTypeWithId(ID)))
+                    //
+                    )))))))))));
   };
 
   const auto IteratorParam = parmVarDecl(
diff --git a/clang-tools-extra/docs/ReleaseNotes.rst b/clang-tools-extra/docs/ReleaseNotes.rst
--- a/clang-tools-extra/docs/ReleaseNotes.rst
+++ b/clang-tools-extra/docs/ReleaseNotes.rst
@@ -291,6 +291,10 @@
   <clang-tidy/checks/performance/no-automatic-move>` when warning would be
   emitted for a const local variable to which NRVO is applied.
 
+- Improved :doc:`bugprone-fold-init-type
+  <clang-tidy/checks/bugprone/fold-init-type>` to handle iterators that do not
+  define `value_type` type aliases.
+
 Removed checks
 ^^^^^^^^^^^^^^
 
diff --git a/clang-tools-extra/test/clang-tidy/checkers/bugprone/fold-init-type.cpp b/clang-tools-extra/test/clang-tidy/checkers/bugprone/fold-init-type.cpp
--- a/clang-tools-extra/test/clang-tidy/checkers/bugprone/fold-init-type.cpp
+++ b/clang-tools-extra/test/clang-tidy/checkers/bugprone/fold-init-type.cpp
@@ -1,39 +1,67 @@
-// RUN: %check_clang_tidy %s bugprone-fold-init-type %t
+// RUN: %check_clang_tidy %s bugprone-fold-init-type -std=c++17 %t
 
 namespace std {
 template <class InputIt, class T>
-T accumulate(InputIt first, InputIt last, T init);
+T accumulate(InputIt first, InputIt last, T init) {
+  // When `InputIt::operator*` returns a deduced `auto` type that refers to a
+  // dependent type, the return type is deduced only if `InputIt::operator*`
+  // is instantiated. In practice this happens somewhere in the implementation
+  // of `accumulate`. For tests, do it here.
+  (void)*first;
+}
 
 template <class InputIt, class T>
-T reduce(InputIt first, InputIt last, T init);
+T reduce(InputIt first, InputIt last, T init) { (void)*first; }
 template <class ExecutionPolicy, class InputIt, class T>
 T reduce(ExecutionPolicy &&policy,
-         InputIt first, InputIt last, T init);
+         InputIt first, InputIt last, T init) { (void)*first; }
 
 struct parallel_execution_policy {};
 constexpr parallel_execution_policy par{};
 
 template <class InputIt1, class InputIt2, class T>
 T inner_product(InputIt1 first1, InputIt1 last1,
-                InputIt2 first2, T value);
+                InputIt2 first2, T value) { (void)*first1; (void)*first2; }
 
 template <class ExecutionPolicy, class InputIt1, class InputIt2, class T>
 T inner_product(ExecutionPolicy &&policy, InputIt1 first1, InputIt1 last1,
-                InputIt2 first2, T value);
+                InputIt2 first2, T value) { (void)*first1; (void)*first2; }
 
 } // namespace std
 
 struct FloatIterator {
-  typedef float value_type;
+  const float &operator*() const;
 };
+
+struct DerivedFloatIterator : public FloatIterator {
+};
+
+template <typename ValueType> struct ByValueTemplateIterator {
+  ValueType operator*() const;
+};
+
+template <typename ValueType> struct ByRefTemplateIterator {
+  ValueType &operator*();
+};
+
+template <typename ValueType> struct ByRefTemplateIteratorWithAlias {
+  using reference = const ValueType&;
+  reference operator*();
+};
+
+template <typename ValueType> struct AutoByValueTemplateIterator {
+  auto operator*() const { return ValueType{}; }
+};
+
+template <typename ValueType> struct AutoByRefTemplateIterator {
+  decltype(auto) operator*() const { return value_; }
+  ValueType value_;
+};
+
 template <typename ValueType>
-struct TypedefTemplateIterator { typedef ValueType value_type; };
-template <typename ValueType>
-struct UsingTemplateIterator { using value_type = ValueType; };
-template <typename ValueType>
-struct DependentTypedefTemplateIterator { typedef typename ValueType::value_type value_type; };
-template <typename ValueType>
-struct DependentUsingTemplateIterator : public TypedefTemplateIterator<ValueType> { using typename TypedefTemplateIterator<ValueType>::value_type; };
+struct InheritingByConstRefTemplateIterator
+    : public ByRefTemplateIterator<const ValueType> {};
+
 using TypedeffedIterator = FloatIterator;
 
 // Positives.
@@ -51,39 +79,57 @@
 }
 
 int accumulatePositive3() {
+  DerivedFloatIterator it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
+}
+
+int accumulatePositive4() {
   double a[1] = {0.0};
   return std::accumulate(a, a + 1, 0.0f);
   // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'double' into type 'float'
 }
 
-int accumulatePositive4() {
-  TypedefTemplateIterator<unsigned> it;
+int accumulatePositive5() {
+  ByValueTemplateIterator<unsigned> it;
   return std::accumulate(it, it, 0);
   // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
 }
 
-int accumulatePositive5() {
-  UsingTemplateIterator<unsigned> it;
+int accumulatePositive6() {
+  ByRefTemplateIterator<unsigned> it;
   return std::accumulate(it, it, 0);
   // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
 }
 
-int accumulatePositive6() {
-  DependentTypedefTemplateIterator<UsingTemplateIterator<unsigned>> it;
+int accumulatePositive7() {
+  AutoByValueTemplateIterator<unsigned> it;
   return std::accumulate(it, it, 0);
   // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
 }
 
-int accumulatePositive7() {
+int accumulatePositive8() {
   TypedeffedIterator it;
   return std::accumulate(it, it, 0);
   // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'float' into type 'int'
 }
 
-int accumulatePositive8() {
-  DependentUsingTemplateIterator<unsigned> it;
+int accumulatePositive9() {
+  InheritingByConstRefTemplateIterator<unsigned> it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
+}
+
+int accumulatePositive10() {
+  AutoByRefTemplateIterator<unsigned> it;
   return std::accumulate(it, it, 0);
-  // FIXME: this one should trigger too.
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
+}
+
+int accumulatePositive11() {
+  ByRefTemplateIteratorWithAlias<unsigned> it;
+  return std::accumulate(it, it, 0);
+  // CHECK-MESSAGES: [[@LINE-1]]:10: warning: folding type 'unsigned int' into type 'int'
 }
 
 int reducePositive1() {
@@ -133,7 +179,7 @@
 }
 
 int negative4() {
-  TypedefTemplateIterator<unsigned> it;
+  ByValueTemplateIterator<unsigned> it;
   // For now this is OK.
   return std::accumulate(it, it, 0.0);
 }