Der Name weist auf den im 14. Jh. von der Lenne abgezweigten Mühlengraben hin, dessen Wasser z. B. 1804 hier eine Getreide- und eine Fingerhutsmühle antrieb, also eine Fabrik, die Fingerhüte herstellte. Später diente der Mühlengraben zeitweise als Abwasserkanal. Dieser wurde 1954 zugeschüttet. Der untere (südliche) Teil der Grabenstraße hieß im Volksmund „Rimplerei“ nach dem hier gelegenen Betrieb des Lohgerbers Rimpler.
Auch in Iserlohn befand sich vor 1975 eine „Grabenstraße“. Sie lag vor der nördlichen Stadtmauer mit dem Stadtgraben. Die „Grabenstraße“ verlief außerhalb des doppelten Mauerrings von der Unnaer Straße, dem heutigen Theodor-Heuss-Ring, hinauf bis zum Nolten. Hier stand auch das erste Spritzenhaus der Freiwilligen Bürgerfeuerwehr. Die Straße führte dann weiter durch den heutigen Nordengraben zwischen Sparkasse und der Dresdner Bank bis zum Schillerplatz.
2019 im Auftrag des Stadtarchivs Iserlohn redigierter Auszug aus:
Holtmeier, Hermann; Reinertz, Manfred: Iserlohner Straßennamen erzählen, hrsg. vom Förderverein Iserlohner Museen e.V., Iserlohn 2009 (Beiträge zur Heimatkunde für Iserlohn und den märkischen Raum; Band 19)