Division ett-ledarna började dag fyra på 48-3 och jagade 235 för seger.
Steve Eskinazi (30) snodde Jake Ball (4-54) bakom sig och Nick Compton kördes ut för 63 att lämna besökarna 146-5.
Men 58 inte från John Simpson och kapten James Franklins obesegrade 54 såg dem till en seger som lämnade dem en punkt utanför Yorkshire.
Besegra för nedre sidan Notts, som har vunnit bara en gång i mästerskapet den här säsongen, innebär att de kommer att spela Division Two cricket 2017 för första gången på ett decennium.
Seger för Middlesex behöll sitt oslagbara rekord i fyra dagars cricket under 2016, även om andra plats Yorkshire 23-punkts seger över Durham minskade Middlesex ledning på toppen med tre poäng.
Somerset, vinnare inom tre dagar över Warwickshire denna vecka, är 22 poäng bakom Middlesex i tredje.
Middlesex spelar Lancashire på Old Trafford nästa vecka, medan Yorkshire underhåller Somerset på Rubrikeley.
Middlesex träffa Yorkshire på Lord's i en potentiell titel beslutsfattare från och med tisdagen den 20 september.
Trots Middlesex blygsamma mål i Nottingham, bollens genombrott och Comptons utkörning efter en förväxling på slag av lunch lämnade spelet i balans.
Men den komponerade Simpson, som tog upp sitt sjätte halvsekel av sommaren, och 35-årige Franklin förseglade segern med en obruten ställning på 89.
Compton, som tog en två månaders paus från cricket i sommar, sade till BBC Radio London: "Jag var stolt över hur jag lyckades hålla ihop saker och ting.
"Som någon som är stolt över svåra situationer, Jag ville se till att jag var på det.
"Syftet var att se till att vi hittade ett sätt att göra det, eftersom det är dags.
"Du får inte alltför många möjligheter att vara en county spelare spelar för titeln som denna fas av säsongen. Det är en fantastisk plats att vara på."
Notts chef för cricket Mick Newell, som kommer att överlämna första lag coaching uppgifter till före detta England tränare Peter Moores i slutet av säsongen, sade: "Det handlar om förlägenheten av att bli förvisade.
– Ekonomiskt sett gör det ingen stor skillnad. Det handlar mer om den inverkan det har på spelarnas ego och påverkan på supportrarna som är vana vid att se Division One cricket.
"Vi är stolta klubb; vi har varit i Division One under en lång tid och det är 10 år sedan jag stod här och var tvungen att förklara bort en nedflyttning."
Middlesex behöll sitt bud på en första County Championship titel sedan 1993 och förvisade Nottinghamshire med en fem-wicket seger på Trent Bridge.