Si l'essentiel de l'oeuvre de Tietze est consacrée à la topologie, il s'appliqua aussi aux problèmes de constructibilité de la géométrie élémentaire (construction à la règle et au compas) et aux développements en fraction continue.
Mais surtout, Tietze joua un rôle de premier plan dans l'avénement de la topologie.
Partant du problème de la coloration des cartes, il établit un premier résultat sur les domaines adjacents d'une surface orientée. Il produisit également une démonstration élémentaire (que l'on trouve reproduite dans plusieurs livres de casse-têtes mathématiques) du fait que le Théorème des quatre couleurs n'a pas d'équivalent dans les dimensions supérieures à 2.
Il généralisa aussi le Théorème de Jordan en montrant que tout fonction continue restreinte à un ensemble fermé d'un espace de dimension finie peut être prolongée en une fonction continue définie sur tout cet espace (théorème de prolongement de Tietze). Tietze développa également la théorie des nœuds en s'appuyant sur les méthodes de la théorie combinatoire des groupes.
En 1908, il se servit de la notion de groupe fondamental et de groupes d’homologie, introduits dès 1895 par Henri Poincaré, pour classer les espaces topologiques. Tietze eut recours aux générateurs et à leurs relations pour produire une représentation du groupe fondamental et exhiba (à l’aide des applications dites « de Tietze » entre les diverses représentations du groupe fondamental) leurs invariants topologiques. C'est dans ce cadre qu'il formula le problème d'isomorphisme pour les groupes (à savoir : « existe-t-il un algorithme permettant de décider si deux groupes définis par un nombre fini d'invariants et de relations sont isomorphes? »). Poincaré avait essayé d'identifier les invariants topologiques à l'aide des groupes homologiques en montrant qu'ils restent invariants lorsque l'on raffine la triangulation de l'espace. Il se posait alors le problème de savoir si ces triangulations sont topologiquement discernables, ce que Poincaré avait implicitement admis. Tietze montra que cela n'était qu'une pure hypothèse, qui devint bientôt dans l'histoire de la topologie la conjecture fondamentale (Hauptvermutung : le mot est de Hellmuth Kneser). Elle ne reçut sa première démonstration (resp. sa première réfutation pour les dimensions supérieures) que dans les années 1960 avec les travaux de John Milnor, Dennis Sullivan, et Robion Kirby parmi d'autres.
C'est en s'appuyant sur la notion d'espace lenticulaire introduite par Tietze qu'en 1919 le mathématicien James Waddell Alexander parvint à réfuter une conjecture de Poincaré, car ils donnaient un exemple d'espaces non-homéomorphes ayant même groupe fondamental.
Il vulgarisa la recherche de son temps dans un livre inédit en français, « Problèmes anciens et modernes, résolus et non-résolus » (Gelöste und ungelöste Probleme aus alter und neuer Zeit, Munich, 1949).