Hlavným hrdinom príbehu je Quentin Jacobsen, obyčajný, spoľahlivý a trochu nesmelý stredoškolák, ktorý celý život tajne zbožňuje svoju susedu Margo Roth Spiegelmanovú – tajomnú, dobrodružnú a charizmatickú dievčinu, ktorá je preňho doslova záhadou.
Dej sa rozbieha, keď jedného večera Margo nečakane vylezie Quentinovi do izby oknom a požiada ho, aby jej pomohol s „nočnou misiou“. Spolu sa vydajú na výpravu za pomstou voči ľuďom, ktorí Margo zradili alebo sklamali – natierajú auto sprejom, robia malé žartíky, vniknú do domu jej bývalého priateľa. Je to nezabudnuteľná noc, v ktorej sa Quentin cíti ako niekto výnimočný, mysliac si, že konečne k sebe našli cestu.
Na druhý deň však Margo zmizne.
Škola aj rodina si myslia, že je to len ďalší z jej výstrelkov, no Quentin cíti, že tentokrát je to vážnejšie. Začne po nej pátrať – nachádza indície, ktoré mu Margo zanechala, ako napríklad knihu „Spev o sebe“ od Walta Whitmana s podčiarknutými pasážami. Pomocou týchto stôp Quentin začína odhaľovať, kam by mohla smerovať – a čo tým vlastne Margo chce povedať.
Postupne si uvedomuje, že Margo vytvorila obraz o sebe, ktorý nikto úplne nepozná. Ani on, ani jej priatelia, ani jej rodičia. Quentin začína chápať, že možno nie je tou výnimočnou dievčinou z dobrodružných legiend – ale obyčajným dievčaťom, ktoré uteká od sveta, v ktorom sa necíti byť naozaj videná.
Spolu s priateľmi Benom, Radarom a Lacey (bývalou Margo kamarátkou) sa vydáva na šialenú cestu autom naprieč Amerikou, ktorá trvá 21 hodín, aby ju našli v opustenom „papierovom“ meste zvanom Agloe, ktoré pôvodne existovalo len ako fiktívne miesto vytvorené kartografmi, ale neskôr sa stalo reálnym.
V závere príbehu Quentin Margo nájde. Žije sama v starom dome a nechce, aby ju niekto hľadal – ušla preto, aby mohla nájsť samu seba. Neplánovala, že ju Quentin naozaj nájde. V rozhovore medzi nimi vychádza najavo, že Quentin ju nikdy skutočne nepoznal – zamiloval sa do predstavy, nie do reality. Margo je nahnevaná, smutná, ale aj slobodná.
Margo sa rozhodne ostať, Quentin sa vráti domov – medzi nimi je tiché pochopenie, že každý si ide svojou cestou. Ich cesty sa skrížili, ale neboli predurčené zostať spolu.
Papierové mestá sú knihou o ideáloch vs. realite. O tom, ako si ľudia vytvárajú obrazy o druhých – často nepravdivé, „papierové“. Margo nie je múza, Quentin nie je hrdina. Ale obaja sú ľudia, ktorí sa učia vidieť iných takých, akí naozaj sú. Kniha ukazuje, že niekedy musíme niekoho nasledovať, aby sme zistili, že sme celý čas hľadali len seba. Záver nie je romantický, ale pravdivý – a práve preto silný.