Index: /trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 18130)
+++ /trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 18131)
@@ -42,4 +42,5 @@
         String newEntry = o.getValue();
 
+        boolean alreadyAdded = false;
         // if history contains this object already, delete it,
         // so that it looks like a move to the top
@@ -47,10 +48,17 @@
             String oldEntry = getElementAt(i).getValue();
             if (oldEntry.equals(newEntry)) {
-                removeElementAt(i);
+                if (i == 0) {
+                    alreadyAdded = true;
+                    break;
+                } else {
+                    removeElementAt(i);
+                }
             }
         }
 
-        // insert element at the top
-        insertElementAt(o, 0);
+        if (!alreadyAdded) {
+            // insert element at the top
+            insertElementAt(o, 0);
+        }
 
         // remove an element, if the history gets too large
Index: /trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java	(revision 18130)
+++ /trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java	(revision 18131)
@@ -6,4 +6,5 @@
 import javax.swing.text.JTextComponent;
 
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletingComboBox;
 import org.openstreetmap.josm.spi.preferences.Config;
@@ -55,5 +56,11 @@
      */
     public void addCurrentItemToHistory() {
-        model.addElement(getEditor().getItem().toString());
+        Object item = getEditor().getItem();
+        // This avoids instantiating multiple AutoCompletionItems
+        if (item instanceof AutoCompletionItem) {
+            model.addElement((AutoCompletionItem) item);
+        } else {
+            model.addElement(item.toString());
+        }
     }
 
Index: /trunk/test/unit/org/openstreetmap/josm/gui/widgets/HistoryComboBoxTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/gui/widgets/HistoryComboBoxTest.java	(revision 18130)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/widgets/HistoryComboBoxTest.java	(revision 18131)
@@ -45,3 +45,25 @@
         assertDoesNotThrow(historyComboBox::addCurrentItemToHistory);
     }
+
+    /**
+     * Non-regression test for JOSM #21215: StackOverflowError
+     */
+    @Test
+    void testNonRegression21215() {
+        final HistoryComboBox historyComboBox = new HistoryComboBox();
+        // utils plugin2 added a listener that pretty much did this
+        historyComboBox.addItemListener(event -> historyComboBox.addCurrentItemToHistory());
+        final AutoCompletionItem testItem = new AutoCompletionItem("testNonRegression21215");
+        // Add the original item
+        historyComboBox.getEditor().setItem(testItem);
+        historyComboBox.addCurrentItemToHistory();
+
+        // add a new item
+        historyComboBox.getEditor().setItem(new AutoCompletionItem("testNonRegression21215_2"));
+        historyComboBox.addCurrentItemToHistory();
+
+        // Readd the first item
+        historyComboBox.getEditor().setItem(testItem);
+        assertDoesNotThrow(historyComboBox::addCurrentItemToHistory);
+    }
 }