Hullkeeper Eldin Jakupovic sparade två straff efter att värdarna hade spelat hela den extra tiden med 10 män efter Dieumerci Mbokanis uppsägning.
Newcastle hade tagit ledningen i extra tid när Mohamed Diame stack hem Vurnon Anita kors för att göra mål mot hans tidigare klubb.
Ledaren varade en minut, Robert Snodgrass utjämnande efter Matz Sels hade spillt Markus Henriksens skott i hans väg.
Mbokani sändes iväg i 89:e minuten för att gå framåt med huvudet på Jamaal Lascelles.
Slipsen kom bara till liv i extra tid, de första 90 minuterna med bara två skott på målet.
Newcastle har nu förlorat nio av sina 10 straff straffar i alla tävlingar, men Rafael Benitez sida kommer att undra varför de inte vann slipsen på 120 minuter.
De hade 32 skott på den tiden, men deras avslutning var lika egensinnig som deras straff.
Jonjo Shelvey satte tonen för Newcastle's spot-kick mardröm när hans försök hölls ute av Jakupovic.
Hulls första straff föll på Snodgrass och han gjorde inget misstag, innan Dwight Gayle kom till baren med sitt försök för Newcastle.
Skipper Michael Dawson gjorde det 2-0 innan Christian Atsu gjorde mål för Newcastle.
Tom Huddlestone gjorde det 3-1, och Hulls spelare och fans firade en första EFL Cup semifinal framträdande när Jakupovic höll ut Yoan Gouffran tama försök.
Hull hade bara ett skott på målet i normal tid, och deras förhoppningar om att nå semifinalen tittade över när Mbokani skickades iväg.
Den framåt, på lån från Dynamo Kiev, sparkade ut och knuffade Lascelles innan lunging framåt vid Newcastle försvarare med huvudet.
31-åringen har dykt upp i fem ligamatcher sedan anländer i slutet av augusti.
Han står nu inför ett tre-match förbud - något Hull kunde göra utan som de ser att klättra bort från Premier League relegation zon.
Hull City boss Mike Phelan: "Detta är den längsta klubben någonsin har varit och spelarna är verkligen nöjda.
"För denna fotbollsklubb, är det en enorm prestation. Förhoppningsvis kan vi gå ett steg längre nu."
Newcastle manager Rafael Benitez: "Det sätt som vi spelade vi förtjänade att göra mål i första halvlek och i extra tid. Sedan när vi gjorde mål målet vi inte hantera situationen.
"Det är något man lär sig med erfarenhet. Kanske kommer vi att göra lite bättre nästa gång vi har så här många chanser."
Newcastle har inte mycket tid att damma ner sig. Magpies återgår till Championship action på fredag bort till Nottingham Forest (19:45 GMT). Middlesbrough väntar Hull i Premier League vid Riverside nästa måndag (20:00 GMT).
Matchändar, Hull City 1.3, Newcastle United 1.1.
Straffet slutar, Hull City 1.3, Newcastle United 1.1.
Straffet är räddat! Yoan Gouffran (Newcastle United) misslyckas med att utnyttja denna stora möjlighet, höger fotade skott räddade i nedre vänstra hörnet.
Mål!  Skrovstad 1.3, Newcastle United 1.1. Tom Huddlestone (Hull City) konverterar straffet med en höger fotad skott till nedre vänstra hörnet.
Mål!  Skrovstad 1.2, Newcastle United 1.1. Christian Atsu (Newcastle United) konverterar straffet med en vänster fotad skott till den höga mitten av målet.
Mål!  Skrovstad 1.2, Newcastle United 1. Michael Dawson (Hull City) konverterar straffet med en högerfotad skott till nedre vänstra hörnet.
Straffet missades! Fortfarande Hull City 1.1, Newcastle United 1. Dwight Gayle (Newcastle United) träffar baren med ett högerfött skott.
Mål!  Skrovstad 1.1, Newcastle United 1. Robert Snodgrass (Hull City) konverterar straffet med en vänster fotad skott till övre högra hörnet.
Straffet är räddat! Jonjo Shelvey (Newcastle United) misslyckas med att utnyttja denna stora möjlighet, högerfotade skott räddade i nedre högra hörnet.
Straffet Shootout börjar Hull City 1, Newcastle United 1.
Andra halv extra tid slutar, Hull City 1, Newcastle United 1.
Försök missade. DeAndre Jedlin (Newcastle United) höger fotade skott från höger sida av lådan är för hög.
Försök blockerat. Yoan Gouffran (Newcastle United) vänster fotade skott från mitten av lådan är blockerad. Hjälpt av Jamaal Lascelles.
Försök blockerat. Mohamed Diamé (Newcastle United) höger fotade skott utanför lådan är blockerad.
Försök missade. Dwight Gayle (Newcastle United) höger fotade skott från mitten av lådan är för hög. Hjälpt av Christian Atsu med ett huvudkort.
Försök missade. Akhraf Lazaar (Newcastle United) vänster fotade skott utanför lådan är bara lite för hög. Hjälpt av Jonjo Shelvey efter ett hörn.
Hörnet, Newcastle United. Förföljd av Michael Dawson.
Hörnet, Newcastle United. Förföljd av Josh Tymon.
Försök missade. Markus Henriksen (Hull City) höger fotade skott från vänster sida av lådan är bara lite för hög. Hjälpt av Adama Diomande efter en viss situation.
Försök missade. David Meyler (Hull City) höger fotade skott från höger sida av lådan missar till vänster efter en set bit situation.
Foul av Mohamed Diamé (Newcastle United).
Adama Diomande (Hull City) vinner en frispark på vänsterflygeln.
Försök missade. Dwight Gayle (Newcastle United) vänster fotade skott från mitten av lådan är hög och bred till vänster. Hjälpt av Christian Atsu.
Ersättning, Newcastle United. DeAndre Jedlin ersätter Vurnon Anita.
Hörnet, Newcastle United. Förföljd av Michael Dawson.
Försök blockerat. Yoan Gouffran (Newcastle United) vänster fotade skott från mitten av lådan är blockerad.
Försök blockerat. Jamaal Lascelles (Newcastle United) huvud från mitten av rutan är blockerad. Hjälpt av Jonjo Shelvey med ett kors.
Hörnet, Newcastle United. Förföljd av Josh Tymon.
Försöket räddades. Dwight Gayle (Newcastle United) header från mitten av rutan sparas i toppen av målet. Hjälpt av Christian Atsu med ett kors.
Andra halv extra tid börjar Hull City 1, Newcastle United 1.
Ersättning, Newcastle United. Daryl Murphy ersätter Isaac Hayden.
Första halvtiden tar slut, Hull City 1, Newcastle United 1.
Försök missade. Josh Tymon (Hull City) höger fotade skott från utanför lådan missar till vänster. Hjälpt av Robert Snodgrass.
Foul av Ciaran Clark (Newcastle United).
Michael Dawson (Hull City) vinner en frispark i den defensiva halvan.
Försök blockerat. Yoan Gouffran (Newcastle United) vänster fotade skott från mitten av lådan är blockerad.
Försök blockerat. Isaac Hayden (Newcastle United) höger fotade skott utanför lådan är blockerad.
Hörnet, Newcastle United. Förföljd av David Meyler.
Försök missade. Jonjo Shelvey (Newcastle United) höger fotade skott från utsidan lådan är hög och bred till höger. Hjälpt av Mohamed Diamé.
Mål!  Skrov City 1, Newcastle United 1. Robert Snodgrass (Hull City) vänster fotade skott från mitten av lådan till mitten av målet.
Newcastle United missade tre spot-kicks som Hull City slog Championship ledare 3-1 på straff för att nå EFL Cup semifinal.