Olekupõhine tulemüür on arvuti või ruuter, mis suudab dünaamiliselt jälgida ja filtreerida sellesse jõudvat liiklust. Seda arhitektuuri nimetatakse olekupõhise pakettide kontrolliks (SPI) või dünaamiliseks pakettide filtreerimiseks. See võimaldab andmepakette kontrollida põhjalikumalt kui olekuta tulemüürid, mis suudavad jälgida liiklust ainult staatiliste väärtuste, näiteks paketi päritolu aadressi alusel. Olekupõhiseid tulemüüre kasutatakse siis, kui kiirusele eelistatakse turvalisust.
Arvutitevaheliseks suhtlemiseks kasutatav Interneti ja üldiselt võrkude protokoll on ehitatud kihtidena. Enamikul tulemüüri kaudu tuleval liiklusel on päis või esialgne pakett, mis tuvastab, mille jaoks see on mõeldud, kuhu see läheb ja mis tüüpi liiklus see on. Seisukohata tulemüür suudab vaadata ainult paketi päist, mis asub kõige pealiskaudses kihis. Olekupõhine tulemüür võib minna sügavamale protokolli teistesse kihtidesse ja rääkida paketi kohta rohkem, muutes selle dünaamilisemaks.
Seisukohata tulemüür vaatab tavaliselt liiklust, mis sellega kokku puutub, ja filtreerib selle, kasutades sellist teavet nagu aadress, kuhu see suunatakse, aadress, kust see tuli, ja muud eelmääratletud statistikat. See on kõige lihtsamat tüüpi tulemüür ja seda on kõige lihtsam kasutada; enamik tarkvarapõhiseid tulemüüre kasutab seda tehnoloogiat. See pole nii turvaline kui olekupõhine tulemüür, kuid see on tavaliselt kiirem, kuna see ei pea töötlema nii palju teavet.
Olekupõhine tulemüür ei saa mitte ainult paketti põhjalikumalt uurida, välistades võimaluse, et pakett teeskleb seda, mida ta ei ole, ja võib-olla põhjustab kahju, vaid suudab jälgida ka sissetuleva ja väljamineva liikluse ühenduse olekuid. See hoiab teavet tabelis, mida nimetatakse olekutabeliks, mis võimaldab filtreerida ja suunata liiklust üksikasjalikuma teabe, näiteks paketi suuruse ja ühenduse protsessi osa põhjal. See muudab olekupõhised tulemüürid tõhusam selle poolest, et nad ei pea iga ühenduse osa pakette uuesti kontrollima, nad saavad lihtsalt kontrollida olekutabelit; palju kiirem protsess, vähemalt turvalisuse huvides. Üldiselt on need turvalisemad kui olekuta tulemüürid, kuid üldiselt on need aeglasemad.
Igal tulemüüritüübil on oma sobiv kasutus. Kodukasutajale, kellel on ainult üks arvuti, sobib hästi olekuteta tulemüür, mis on nagunii enamikesse operatsioonisüsteemidesse sisse ehitatud; olekupõhine tulemüür võib süsteemi aeglustada. Suuremate võrkude, näiteks suurte ettevõtete või asutuste jaoks oleks olekupõhine tulemüür parem valik. Kiiruse vähenemise korvab tavaliselt asjaolu, et tulemüür on riistvaraline ning sellel on oma protsessor ja mälu.