diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -21,7 +21,7 @@
     GROUP_BASE_NAME KF
     VERSION ${KF5_VERSION}
     DEPRECATED_BASE_VERSION 0
-    DEPRECATION_VERSIONS 4.0 4.5 5.0 5.46
+    DEPRECATION_VERSIONS 4.0 4.5 5.0 5.46 5.66
     EXCLUDE_DEPRECATED_BEFORE_AND_AT ${EXCLUDE_DEPRECATED_BEFORE_AND_AT}
 )
 
diff --git a/src/khistorycombobox.h b/src/khistorycombobox.h
--- a/src/khistorycombobox.h
+++ b/src/khistorycombobox.h
@@ -25,6 +25,8 @@
 #include <kcombobox.h>
 #include <kcompletion_export.h>
 
+#include <functional>
+
 class KPixmapProvider;
 class KHistoryComboBoxPrivate;
 
@@ -172,15 +174,28 @@
      * Set @p provider to nullptr if you want to disable pixmaps. Default no pixmaps.
      *
      * @see pixmapProvider
+     * @deprecated since 5.66, use setIconProvider
      */
+#if KCOMPLETION_ENABLE_DEPRECATED_SINCE(5, 66)
+    KCOMPLETION_DEPRECATED_VERSION(5, 66, "Use setIconProvider")
     void setPixmapProvider(KPixmapProvider *provider);
 
     /**
      * @returns the current pixmap provider.
      * @see setPixmapProvider
      * @see KPixmapProvider
+     * @deprecated since 5.66, unused
      */
+    KCOMPLETION_DEPRECATED_VERSION(5, 66, "unused")
     KPixmapProvider *pixmapProvider() const;
+#endif
+
+    /**
+     * Sets an icon provider, so that items in the combobox can have an icon.
+     * The provider is a function that takes a QString and returns a QIcon
+     * @since 5.66
+     */
+    void setIconProvider(std::function<QIcon(const QString &)> providerFunction);
 
     using QComboBox::insertItems;
 
diff --git a/src/khistorycombobox.cpp b/src/khistorycombobox.cpp
--- a/src/khistorycombobox.cpp
+++ b/src/khistorycombobox.cpp
@@ -76,6 +76,8 @@
      */
     bool rotated = false;
 
+    std::function<QIcon(QString)> iconProvider;
+
     Q_DECLARE_PUBLIC(KHistoryComboBox)
 };
 
@@ -237,7 +239,9 @@
     }
 
     // now add the item
-    if (d->pixmapProvider) {
+    if (d->iconProvider) {
+        insertItem(0, d->iconProvider(item), item);
+    } else if (d->pixmapProvider) {
         insertItem(0, d->pixmapProvider->pixmapFor(item, iconSize().height()), item);
     } else {
         insertItem(0, item);
@@ -408,6 +412,7 @@
     ev->accept();
 }
 
+#if KCOMPLETION_BUILD_DEPRECATED_SINCE(5, 66)
 void KHistoryComboBox::setPixmapProvider(KPixmapProvider *provider)
 {
     Q_D(KHistoryComboBox);
@@ -427,6 +432,13 @@
         insertItems(items);
     }
 }
+#endif
+
+void KHistoryComboBox::setIconProvider(std::function<QIcon(const QString &)> providerFunction)
+{
+    Q_D(KHistoryComboBox);
+    d->iconProvider = providerFunction;
+}
 
 void KHistoryComboBox::insertItems(const QStringList &items)
 {
@@ -437,7 +449,9 @@
             continue;
         }
 
-        if (d->pixmapProvider) {
+        if (d->iconProvider) {
+            addItem(d->iconProvider(item), item);
+        } else if (d->pixmapProvider) {
             addItem(d->pixmapProvider->pixmapFor(item, iconSize().height()), item);
         } else {
             addItem(item);
@@ -482,11 +496,13 @@
     }
 }
 
+#if KCOMPLETION_BUILD_DEPRECATED_SINCE(5, 66)
 KPixmapProvider *KHistoryComboBox::pixmapProvider() const
 {
     Q_D(const KHistoryComboBox);
     return d->pixmapProvider;
 }
+#endif
 
 void KHistoryComboBox::reset()
 {