La rue porte un nom vieux de plus de six siècles. Un lieu-dit « Tiquetonne » apparaît dès le censier de 1372, et en 1399 un certain Roger Tiquetonne y est attesté comme résident — suffisant pour que le toponyme s'accroche durablement à la voie, malgré les variantes orthographiques qui l'ont fait écrire « Quiquetonne » ou « Tictonne ». Avant de s'appeler ainsi, le tronçon côté Saint-Denis répondait aux noms de rue Pavée, puis rue du Petit-Lion-Saint-Sauveur ; l'autre partie portait le nom de rue Denis-le-Coffrier. C'est un arrêté du 2 avril 1868 qui soude les deux tronçons en une seule artère de 330 mètres, unissant la rue Saint-Denis à la rue Étienne-Marcel.
Au Moyen Âge, le voisinage est princier : les numéros 21-23 se trouvent à l'emplacement de l'entrée de l'Hôtel de Bourgogne, résidence liée aux ducs — parmi lesquels Jean sans Peur et, dans un passé plus lointain, la lignée de Philippe III le Hardi. En 1613, le no 19 abrite le précepteur de la famille de Gondi, et c'est dans ce cercle que le jeune Vincent de Paul gravite alors. En 1626, Henri de Talleyrand loge aux numéros 60-64 ; sa fin est brutale : Richelieu le fera exécuter pour avoir conspiré deux fois contre lui. Au milieu du XVIIIe siècle, l'atmosphère se fait plus légère — le dramaturge Favart et la comédienne Duronceray habitent au no 13 —, et Rochegude rappelle que le célèbre Scaramouche était mort rue Tictonne en 1694.
Mais c'est à l'ère révolutionnaire que la rue devient un foyer de presse combattante. Au no 7 fonctionne en 1792-1793 l'imprimerie du conventionnel Antoine-Joseph Gorsas, qui y publie son Courrier des quatre-vingt-trois départements ; ses presses sont fracassées par des émeutiers, et Gorsas sera le premier conventionnel à monter à l'échafaud. Sous le Second Empire puis pendant la guerre de 1870, le no 66 abrite le journal Le Combat de Félix Pyat — saccagé lorsque le gouvernement cherche à dissimuler la capitulation de Bazaine à Metz, Pyat s'enfuyant de justesse. En février 1871, Pyat fonde au même numéro Le Vengeur ; le journal, jugé trop radical, sera paradoxalement interdit par la Commune elle-même avant d'être repris par l'avocat-journaliste Jean-Baptiste Millière, qui en tirera quatre-vingts numéros. La rue Tiquetonne, enfin, est immortalisée dans la fiction : Balzac y place la boutique de sa Maison du chat-qui-pelote au no 1.