Hjärtan dominerade första halvan, Jamie Walker fick en tredje minut straff efter Kevin Gomis fick ner honom.
Callum Paterson åkte hem till Don Cowies frispark tidigt på återupptagandet.
Men Dundee kapten Darren O'Dea borrade hem för att minska underskottet, Paul McGowan slog hem utjämnaren innan Paterson på väg in i sitt eget nät.
Seger, deras fjärde i åtta matcher, lyfte Dark Blues till sjunde plats, medan fjärde-placerade hjärtan är nu utan en seger i fyra.
Winger Walker har varit föremål för mycket diskussion den här säsongen med hans vridningskörningar regelbundet framkallar försvarare i utslag utmaningar inuti lådan.
Och än en gång förtjänade han sitt lag ett straff efter att ha spelats in av Björn Johnsen. 23-åringen plockade upp sig själv för att skicka Scott Bain på fel sätt för sin femte framgångsrika spot-kick, och åttonde målet, för säsongen.
Walker fick i hög grad hjälp av Paterson, som Hearts chef för fotboll Craig Levein sade tidigare i veckan kommer inte att lämna klubben i januari om de inte får ett sjusiffrigt erbjudande.
När Skottland full-back på väg hem Don Cowies fri-kick tre minuter in i den andra perioden, hans åttonde mål för säsongen och 37: e för klubben totalt sett, besökarna såg avsedda för alla tre punkter.
Hemmafansen gjorde sina frustrationer kända som ett femte hem nederlag för säsongen hotade.
Chef Paul Hartley svarade genom att ersätta midfielder Mark O'Hara med Paul McGowan, och dynamiken i spelet förändrades.
O'Dea drog en tillbaka med en sällsynt höger-fot slag efter Hearts försvar misslyckades med att rensa bollen från sin egen låda.
Med förtroende synligt växer, McGowan fastnade på en boll från Craig Wighton och klippte bollen över den avancerande Jack Hamilton för att rita Dundee nivå.
En nackskada på Hjärtans mittfältare Don Cowie, som blev uttöjd efter en försening på sju minuter och förd till sjukhus, tycktes påverka besökarna negativt.
De 1400 Hearts fans som gjorde resan till Dundee kunde knappt tro sitt lags kollaps när värdarna avslutade sin comeback i 93: e minuten, Haber få upp för att träffa en Tom Hateley fri-kick från nära håll, bara för Hearts försvarare Paterson att rikta en rubrik i sitt eget nät.
Hjärtan borde ha varit utom synhåll på halvtid. Paterson, Walker, Arnaud Djoum och Krystian Novak alla kom nära att lägga ytterligare mål till Walkers öppnare, och Cathro måste undra vad hans spelare måste göra för att få den första vinsten av sin anställning.
De har ytterligare två möjligheter nästa vecka före vinteruppehållet, med Kilmarnock - på tisdag - och Aberdeen - nästa fredag - båda besöker Tynecastle.
Dundee chef Paul Hartley:
"Första halvan var vi riktigt fattiga, spelet kunde ha varit död och begravd. Det är det värsta vi har varit på länge.
"Den andra halvan visade vi en riktig grus, beslutsamhet och önskan att stanna i spelet på 2-0 ner och vi trodde alltid att vi skulle få chanser. När vi fick tillbaka målet att göra det 2-1 kunde vi känna momentum bygga.
"Jag är verkligen stolt över spelarna eftersom det har varit en tuff säsong hittills. De visade bra karaktär ikväll. De kunde ha gått in i ett skal, men vi fortsatte. Hjärtan var utmärkta i första halvlek men vi ändrade ett par saker och det lönade sig."
Hearts huvudtränare Ian Cathro:
"Jag visste inte att det skulle komma. Ingen gjorde det. Vi hade full kontroll över spelet. Vår prestation var bra och vi hade en dominerande ställning. I slutändan har vi gjort misstag och kastat bort spelet. Så enkelt är det.
"Det var en paus i spelet, ett par förändringar men allt vi fick i uppdrag att göra var att hantera spelet ordentligt och hålla ihop. Jag tror att alla är medvetna om att det finns unga spelare i laget men det finns några erfarna spelare också. När vi är i dessa positioner måste vi vinna matcherna.
"Det har nu gått två veckor. Jag har lärt mig mycket om alla, om oss. Det enda jag har lärt mig om mig själv är att jag hade rätt när jag för länge sedan trodde att jag var stark nog att ta itu med dessa saker. Jag är självsäker och avslappnad i det faktum och tur att jag är stark och dessa utmaningar bara bidrar till att göra mig lite bättre."
Matchändar, Dundee 3, Midlotians hjärta 2.
Andra halvlek, Dundee 3, Midlotians hjärta 2.
Substitution, Midlotians hjärta. Faycal Rherras ersätter Liam Smith.
Mål!  Dundee 3, Midlotians hjärta 2. Marcus Haber (Dundee) header från mycket nära håll till den höga mitten av målet. Hjälpt av Tom Hateley efter en viss situation.
Liam Smith (Hjärtat av Midlotian) visas det gula kortet för en dålig foul.
Foul av Liam Smith (Hjärtat av Midlotian).
Cameron Kerr (Dundee) vinner en frispark i den defensiva halvan.
Substitution, Midlotians hjärta. Tony Watt ersätter Jamie Walker.
Försöket räddades. Craig Wighton (Dundee) header från mitten av rutan sparas i toppen av målet.
Hörnet, hjärtat av Midlotian. Sammankallad av Kostadin Gadzhalov.
Kevin Holt (Dundee) visas det gula kortet för en dålig foul.
Foul av Kevin Holt (Dundee).
Jamie Walker (Hjärtat av Midlotian) vinner en frispark i defensiva halvan.
Försök missade. Callum Paterson (Hjärtat av Midlotian) vänster fotade skott från utanför lådan missar till vänster.
Försök missade. Craig Wighton (Dundee) vänster fotade skott från vänster sida av lådan är nära, men missar övre vänstra hörnet.
Foul av Julen Etxabeguren Leanizbarrutia (Dundee).
Björn Johnsen (Heart of Midlotian) vinner en frispark på vänsterflygeln.
Tom Hateley (Dundee) vinner en frispark i anfallshalvan.
Foul av Liam Smith (Hjärtat av Midlotian).
Hörnet, Dundee. Förföljd av Robbie Muirhead.
Hörnet, Dundee. Förföljd av Igor Rossi.
Försök blockerat. Tom Hateley (Dundee) höger fotade skott från höger sida av lådan är blockerad.
Försök missade. Callum Paterson (Hjärtat av Midlotian) vänster fotade skott från utanför lådan missar till höger.
Försöket räddades. Robbie Muirhead (Hjärtat av Midlotian) höger fotade skott från utsidan boxen sparas i toppen av målet.
Försök missade. Björn Johnsen (Hjärtat av Midlotian) huvudet från mitten av lådan missar till höger.
Mål!  Dundee 2, Midlotians hjärta 2. Paul McGowan (Dundee) höger fotade skott från mycket nära håll till nedre högra hörnet. Hjälpt av James Vincent.
Substitution, Midlotians hjärta. Robbie Muirhead ersätter Don Cowie på grund av en skada.
Försök missade. Jamie Walker (Heart of Midlothian) vänster fotade skott från mitten av lådan är för hög.
Foul av Arnaud Djoum (Hjärtat av Midlotian).
Kostadin Gadzhalov (Dundee) vinner en frispark i anfallshalvan.
Hörnet, hjärtat av Midlotian. Förföljd av Cameron Kerr.
Mål!  Dundee 1, Midlotians hjärta 2. Darren O'Dea (Dundee) höger fotade skott från mitten av lådan till nedre högra hörnet. Hjälpt av Marcus Haber.
Foul av Igor Rossi (Hjärtat av Midlotian).
Marcus Haber (Dundee) vinner en frispark på högerkanten.
Ersättning, Dundee. Paul McGowan ersätter Mark O'Hara.
Försöket räddades. Björn Johnsen (Hjärtat av Midlotian) höger fotade skott från utsidan boxen sparas i mitten av målet.
Jamie Walker (Heart of Midlothian) vinner en frispark i anfallshalvan.
Foul av Tom Hateley (Dundee).
Mål!  Dundee 0, Midlotians hjärta 2. Callum Paterson (Heart of Midlothian) header från mycket nära till övre vänstra hörnet. Hjälpt av Don Cowie efter en viss situation.
Callum Paterson (Heart of Midlothian) vinner en frispark på högerkanten.
Dundee kom från två mål ner för att bedöva Hearts med en skada-tid vinnare och lämna Ian Cathro fortfarande väntar på sin första seger som huvudtränare.