Robbie Benson tände upp en ojämn första halvlek med en fantastisk söt-skurk höger-fot volley in i övre hörnet från kanten av området.
Värdarna hade Adam Hlousek skickat iväg för ett andra gult kort på 67 minuter.
Michal Kucharczyk utjämnade med en komponerad soloinsats i extra tid.
Dundalk kommer att gå in i Europa League-gruppen stadier, som efterliknar uppnåendet av andra League of Ireland sida Shamrock Rovers 2011. Dragningen görs på fredag.
Legia Warszawa kommer att invänta resultatet av Champions League dra i Monaco på torsdag efter att ha blivit den första klubben från Polen för att nå grupp stadierna i 20 år.
Besökarna, som säkrade en liga och kopp dubbel i Irland förra säsongen, hade kvalificerat sig för kvalificerande play-off genom att besegra vitryska mästare Bate Borisov 3-1 i föregående omgång, med hjälp av en minnesvärd 3-0 second-leg seger.
Dundalk skryter med en befolkning på bara 39.000 och klubben gick in i andra benet av sin slips på polska Army Stadium har redan bankat mer än £ 4m för sina europeiska bedrifter, med mer inställd på att komma när deras europeiska äventyr fortsätter.
Dundalks chanser till progression verkade vara små efter deras 2-0 nederlag i händerna på de polska mästarna i Dublin förra veckan, men Bensons magnifika första halvan strejk var bara belöning för Stephen Kennys sida ansträngningar i öppningshalvan.
Benson hade kommit i sidan för att ersätta suspenderad kapten Stephen O'Donnell och hans perfekt avrättade mål var hans fjärde för säsongen och hans andra i tävlingen.
Benson gick nära för att ta tag i en sekund i 63: e minuten men hans overhead cykel kick, efter David McMillan på väg in i hans väg, flög över baren.
Hlousek fick sin andra bokning fyra minuter senare för att ha släpat ner Ronan Finn men Dundalk kunde inte dra nytta av den extra mannen.
Kucharczyks åskande sena strejk på pausen släckte den irländska sidans förhoppningar och utnyttjade luckorna i deras försvar när de gick framåt i sökandet efter det mål som skulle ha tagit spelet till extratid.
Matchändar, Legia Warszawa 1, Dundalk 1.
Andra halvlek, Legia Warszawa 1, Dundalk 1.
Lukasz Broz (Legia Warszawa) vinner en frispark i defensiva halvan.
Foul av Daryl Horgan (Dundalk).
Foul av Guilherme (Legia Warszawa).
Dane Massey (Dundalk) vinner en frispark på vänster flygel.
Ersättning, Legia Warszawa. Aleksandar Prijovic ersätter Thibault Moulin.
Michal Kucharczyk (Legia Warszawa) visas det gula kortet för överdrivet firande.
Mål!  Legia Warszawa 1, Dundalk 1. Michal Kucharczyk (Legia Warszawa) höger fotade skott från mitten av lådan till nedre högra hörnet. Hjälpt av Vadis Odjidja-Ofoe efter en snabb paus.
Michal Kucharczyk (Legia Warszawa) vinner en frispark i defensiva halvan.
Foul av Patrick Barrett (Dundalk).
Offside, Legia Warszawa. Guilherme försöker en genom boll, men Thibault Moulin fångas offside.
Försöket räddades. Guilherme (Legia Warszawa) vänster fotade skott från mitten av lådan sparas i det övre högra hörnet. Hjälpt av Michal Kucharczyk.
Ersättning, Dundalk. Michael O'Connor ersätter Patrick McEleney.
Försening över. De är redo att fortsätta.
Försening i matchen Guilherme (Legia Warszawa) på grund av en skada.
Offside, Legia Warszawa. Vadis Odjidja-Ofoe försöker en genom boll, men Michal Kucharczyk fångas offside.
Ersättning, Dundalk. Darren Meenan ersätter Chris Shields.
Försök blockerat. Michal Kucharczyk (Legia Warszawa) höger fotade skott utanför lådan är blockerad. Hjälpt av Bartosz Bereszynski.
Försök blockerat. Andrew Boyle (Dundalk) huvud från mitten av rutan är blockerad. Hjälpt av Daryl Horgan med ett kors.
Hörnet, Dundalk. Sammankallad av Igor Lewczuk.
Foul av Thibault Moulin (Legia Warszawa).
Sean Gannon (Dundalk) vinner en frispark i anfallshalvan.
Försöket räddades. Patrick McEleney (Dundalk) höger fotad skott från höger sida av lådan sparas i mitten av målet. Hjälpt av Daryl Horgan.
Hörnet, Legia Warszawa. Förföljd av Sean Gannon.
Försök blockerat. Bartosz Bereszynski (Legia Warszawa) höger fotade skott från vänster sida av lådan är blockerad. Hjälpt av Thibault Moulin.
Robbie Benson (Dundalk) visas det gula kortet för en dålig foul.
Michal Kucharczyk (Legia Warszawa) vinner en frispark på högerkanten.
Foul av Robbie Benson (Dundalk).
Ersättning, Legia Warszawa. Bartosz Bereszynski ersätter Nemanja Nikolic.
Guilherme (Legia Warszawa) vinner en frispark på högerkanten.
Foul av Chris Shields (Dundalk).
Andra gula kortet till Adam Hlousek (Legia Warszawa) för en dålig foul.
Foul av Adam Hlousek (Legia Warszawa).
Ronan Finn (Dundalk) vinner en frispark i den defensiva halvan.
Ersättning, Legia Warszawa. Guilherme ersätter Steeven Langil.
Foul av Igor Lewczuk (Legia Warszawa).
David McMillan (Dundalk) vinner en frispark på vänsterkanten.
Försök missade. Robbie Benson (Dundalk) vänster fotade skott från mitten av lådan är för hög. Hjälpt av David McMillan med ett nyckelkort.
Hörnet, Dundalk. Förföljd av Adam Hlousek.
Dundalks försök att bli den första irländska sidan för att göra Champions League grupp stadier föll precis kort som de förlorade 3-1 till Legia Warszawa på aggregat efter en kreditabel 1-1 dragning i Polen.