Pri navideznem pomnilniku na osnovi segmentacije je pomnilniški prostor razdeljen na dele, ki jim pravimo segmenti. Segmenti so različne velikosti. Druga razlika v primerjavi z ostranjevanjem je ta, da ima vsebina segmenta za program svoj pomen. Število in velikost segmentov nista fiksna in se med izvajanjem programov lahko spreminjata. Segment navideznega pomnilnika se lahko preslika na poljuben naslov v glavnem pomnilniku.

Moderni programski jeziki silijo programerja k temu, da piše programe modularno. Programski moduli so deli programa, ki so med seboj razližno povezani. Pri navideznem pomnilniku na osnovi segmentacije, je vsak program viden kot zbirka med seboj povezanih segmentov. Pri prehajanju iz enega segmenta v drugega so običajno predpisane omejitve, ki zagotavljajo integriteto segmentov. Segmentu ni dovoljeno dostopati do ukazov in operandov drugega segmenta na enak način kot dostopa do svojih, ampak lahko to stori le na majhno v naprej predpisanih načinov, pri katerih se običajno opravi tudi vrsta preverjanj. Vsak segment ima svoje simbolično ime, pod katerim je znan operacijskemu sistemu.

Segmenti so ukazni (tekst izvornega programa, tabela simbolov, konstant, sklad,...) in podatkovni.

Največja velikost in število segmentov sta iz praktičnih razlogov omejena. Preslikovalna funkcija je realizirana preko tabele segmentov. Velikost tabele ni znana v naprej. Običajno ima vsak program svojo tabelo segmentov, ki je lahko tudi sama en segment. V posebni tabeli so shranjeni naslovi tabel segmentov vseh programov, ki so trenutno v obdelavi.

Vsak program je sestavljen iz določenega števila segmentov. Vsak segment ima v tabeli segmentov svoje polje - deskriptor segmenta. N-bitni navidezni naslov, ki ga tvori CPE sestavlja relativni naslov besede(spodnjih s bitov) v segmentu in številka segmenta (zgornjih n-s bitov). Preslikuje se samo številka segmenta. Parametri v deskriptorju so podobni kot pri ostranjevanju:

• bit prisotnosti P,
• zaščitni ključ RWX - ker ima vsak segment svoj pomen, je zaščita lahko popolnejša,
• bit spremembe C,
• velikost segmenta L - velikost segmenta merjena v številu besed - maksimalna dolžina parametra je s bitov (glej opis navideznega naslova zgoraj),
• naslov segmenta SA - fizični naslov v glavnem pomnilniku.

Tudi pri segmentaciji lahko pride do pojava premetavanja. Ker so različni segmenti različno veliki, je pred prenosom v glavni pomnilnik potrebno najti dovolj velik zvezen prostor, ki pa je skoraj vedno večji od segmenta. To privede do zunanje fragmentacije - med posameznimi segmenti v glavnem pomnilniku se pojavljajo luknje, ki so zaradi svoje majhnosti neuporabne.

Velikost lukenj je nepredvidljiva. Pomembna je izbira algoritma za dodeljevanje glavnega pomnilnika segmentom:

• najboljše ujemanje - razlika med velikostjo segmenta in luknje je najmanjša,
• najslabše ujemanje - razlika med velikostjo segmenta in luknje je največja,
• prvo ujemanje - razlika med velikostjo segmenta in luknje je naključna.

Pri vseh je algoritmih je po določenem času potrebno strnjevanje pomnilnika (defragmentacija), saj je pomnilniški prostor tako fragmentiran, da delo ni več možno.

Še ena slabost segmentacije je ta, da je potrebno vedno v glavni pomnilnik prenesti cel segment, čeprav se potrebuje samo en majhen del le-tega. Zato se več uporablja segmentacija z ostranjevanjem.