La historia del Kohlmarkt se remonta a la época del campamento militar romano de Vindobona. La puerta suroeste de Vindobona, la Porta Decumana (conocida posteriormente como Puerta Peiler), estaba situada en la intersección de los modernos Graben y Tuchlauben. El Kohlmarkt se dirigía hacia el suroeste desde la Porta Decumana, conectándola con la calzada del limes.^[2]​^[3]​^[4]​

En 1255, la calle era conocida con el nombre de el Witmarkt («mercado de madera»). Cuando durante el siglo xiii se construyó al suroeste del mercado una nueva puerta de la ciudad, fue llamada Witmarkttor («puerta del mercado de madera»). El nombre Witmarkt cayó en desuso durante el siglo xiv, cuando la calle pasó a ser designada como Kohlenmarkt («mercado de carbón») debido a sus numerosos vendedores de carbón vegetal. Tras la construcción del Hofburg, el palacio de los emperadores de la Casa de Habsburgo, la cercanía del mercado de carbón a la residencia imperial propició la instalación de productores y vendedores de bienes de alta calidad y de lujo en su lugar. Con el tiempo, el Kohlmarkt se convirtió en una calle de tiendas y procesiones muy representativa. Sin embargo, conservó su antiguo nombre, que evolucionó a Kohlmarkt («mercado de coles»), un nombre engañoso, ya que el mercado nunca ha sido conocido por la venta de coles.^[5]​

Después de que se convirtiera en una calle muy representativa, en el Kohlmarkt han vivido varias figuras culturales importantes. En el siglo xviii, el compositor Joseph Haydn vivió durante varios años en la calle mientras trabajaba como músico acompañante de clases de canto y baile.^[6]​ El poeta Pietro Metastasio y el fabricante de pianos Ludwig Bösendorfer vivieron y murieron en el mismo edificio con más de cien años de diferencia entre sí.^[7]​^[8]​ Durante su época en Viena, entre 1830 y 1831, Frédéric Chopin también vivió en el Kohlmarkt.^[9]​

El Kohlmarkt alberga y ha albergado varias tiendas de alta gama a lo largo del tiempo, incluidas las de antiguos titulares de autorizaciones reales como la pastelería y chocolatería Demel, la tienda de tabaco Mohilla, la librería Manz y la joyería Rozet & Fischmeister.^[10]​ Sin embargo, con el final de la monarquía de los Habsburgo, así como la creciente competencia y el aumento de los alquileres, muchos establecimientos tradicionales se han visto obligados a cerrar. En su lugar, se han instalado en la calle varias marcas internacionales de lujo. Con una renta media de 4620 euros en 2016, el Kohlmarkt es la séptima calle más cara de Europa para locales comerciales y la más cara de Austria.^[11]​

En 1989, el Kohlmarkt fue transformado en una zona peatonal durante la peatonalización del adyacente Graben, que tuvo lugar en fases durante las décadas de 1970 y 1980. Una de las últimas fases incluyó también la peatonalización del Kohlmarkt, lo que llevó al rediseño de la calle.^[12]​

• Varios edificios diseñados parcialmente por Adolf Loos, incluidos:
  • Looshaus (uno de los edificios más significativos de la arquitectura moderna de Viena)^[13]​
  • Librería Manz (portal diseñado por Adolf Loos)
• Palais Blankenstein (palacio neoclásico)^[14]​
• Demel (pastelería y chocolatería, antiguo proveedor de la corte real)^[15]​
• Artaria-Haus (edificio modernista)^[16]​
• Großes Michaelerhaus (edificio de apartamentos del siglo xviii, donde residieron Joseph Haydn, Pietro Metastasio y Ludwig Bösendorfer)^[17]​^[18]​^[19]​
• Husarenhaus (con una estatua de bronce de un húsar a tamaño real en la azotea)^[20]​
• Antiguos grandes almacenes Pollak (con ornamentos diseñados por Koloman Moser)^[21]​

• Czeike, Felix (1994). Historisches Lexikon Wien, Band 3 (en alemán). Viena: Kremayr & Scheriau. ISBN 3-218-00545-0. 
• Engel, Reinhard (2001). Luxus aus Wien I (en alemán). Viena: Czernin Verlag. ISBN 3-7076-0121-8. 

• Artículo sobre el Kohlmarkt en la Vienna History Wiki