La unuaj setlejoj en la areo de la hodiaŭa urbo Zella-Mehlis plej verŝajne ekestis lige kun Oberhof-pasejo, unu el la plej malnovaj kaj plej gravaj transirejoj en la Turingia Arbaro. Arĥeologoj povis pruvi ke ĝi ekzistis jam en la malfrua ŝtonepoko. Trovitaĵoj el la 2-a jarmilo a.K. (sagopinto), la bronzepoko (bronza hakilo), la La-Tène-kulturo (remparoj sur Ruppberg-monto) kaj aliaj aferoj pruvas la longegan ĉeeston de homoj en tiu ĉi valbaseno. La unuaj setlejoj eble devenas el la karolida-liudolfida periodoj; setlada kontinueco klaras ekde la 11-a/12-a jarcentoj. Eble ankaŭ en la kvartalo Mehlis tiam jam estis domaj strukturoj - sed tio dokumente ne klaras.
La unua mencio pri Zella St. Blasii datiĝas el falsita dokumento en 1112. Ĝi konfirmu la konsekron de preĝdomo honore al Sankta Blazio, kiu estis ligita al terdonaco de la nobelo Gebhardt von Nordeck al la benediktana monaĥejo je Reinhardsbrunn. La preĝa domo iĝis prepostejo (latine: Cella Sancti Blasii) en kies ĉirkaŭaĵo aŭtomate disvolviĝis vilaĝo. La vilaĝo Mehlis estis unuafoje menciita en dokumento en 1250, sed ĝia historio tre verŝajne pli reeniras.
Ambaŭ loĝlokoj apartenis al la priorujo de Zella St. Blasii ĝis 1357, kiam la plej granda parto de la monaĥaj havaĵoj de Zella venis en la manojn de la dinastio Wettin kiel landgrafoj de Turingio, per interŝanĝo-interkonsento. Zella St. Blasii restis posedaĵo benediktana, dume Mehlis iĝis landgrafa/wettin-a kvankam ne estu forgesate ke la grafoj de Henneberg ankaŭ havis ampleksajn privilegiojn en Mehlis.
De 1470 ĝis 1525, Mehlis apartenis al la teritorio de la grafoj de Gleichen. Dum la kamparana ribelo batalemoj detruis la klostron en Reinhardsbrunn en 1525. Ĝiaj havaĵoj iĝis sekularaj, sekve ankaŭ Zella St. Blasii. Post 1525, ambaŭ vilaĝoj apartenis al la ernestidaj branĉoj de la Wettin-oj.
En 1645 duko Ernesto la 1-a (Saksio-Gotao) nomumis Zella St. Blasii foirejo kun urbaj privilegioj. En la sama jaro ĝi iĝis la oficiala sidejo de Administradujo Schwarzwald. En 1661 oni sukcese gajnis la antaŭajn Henneberg-rajtojn en Mehlis de la anoj de Saksio-Zeitz, kio finis la logegan dividadon de la urbo. En 1762 fajrego preskaŭ komplete detruis la urbon kaj en 1894 la Mehlis-anoj ricevis urborajtojn.
La 9-an de novembro 1918, Zella St. Blasii kaj Mehlis iĝis parto de la ĵus fondita Popola Respubliko de Gotha kiu poste nomiĝis Liberŝtato Gotha. Tio okazis post kiam la duko de Saksio-Koburgo kaj Gotao estis detronigita en la kuro de Novembra Revolucio.
La 1-an de aprilo 1919, post ses jaroj da intertraktado, unuiĝo inter Zella kaj Mehlis estis perfektigita. En 1920, Zella-Mehlis iĝis municipo en la nove fondita ŝtato de Turingio. De 1919 ĝis 1922 kaj de 1924 ĝis 1935 Zella-Mehlis estis sendependa de distrikto.
Post la fino de la Dua mondmilito la urbo iĝis parto de Subdistrikto Schleusingen (1945). En 1946 ĝi estis renomita Subistrikto Suhl kaj ekde 1952, okaze de administra reformego kaj formiĝo de distriktoj en GDR, la tuto ekestis parto de Distrikto Suhl. En la sama jaro, Zella-Mehlis mem iĝis la subdistrikta ĉefurbo. En 1967 Distrikto Suhl estis renomita Distrikto Suhl-Land. Ankaŭ en komunismaj tempoj Zella-Mehlis konservis sian reputacion kiel nacie grava industria loko kaj talentfabriko, precipe koncerne vintrajn sportojn kaj luktadon.
