Ciudades de papel comienza con Quentin “Q” Jacobsen, de nueve años, y Margo Roth Spiegelman descubren el cadáver de Robert Joyner, un hombre que pronto se divorciará y que se suicidó en Jefferson Park.
Nueve años después, Quentin y Margo se distanciaron el uno del otro considerando que son vecinos. Una noche, Margo aparece en la ventana de Quentin con pintura negra en la cara. Ella le pide a Quentin que la ayude esa noche con once misiones para vengarse de las personas que la han lastimado durante sus años de escuela secundaria. Especialmente necesita el coche de Quentin y la asistencia para conducir. Margo convence a Quentin de que se lleve la minivan de su madre, se escabulle de su casa en una noche escolar y la ayude a buscar venganza.
Margo lleva a Quentin a una aventura llena de peces, vandalismo, pintura en aerosol, irrumpir en SeaWorld y depilar la ceja de un matón mientras duerme. Después de completar sus once cosas, Quentin se alegra de haber vuelto a ser amigo de Margo. Al día siguiente, Margo nunca se presenta a la escuela o los siguientes tres días. Debido a que Margo ya se había escapado de casa, sus padres no tienen preocupaciones, ya que esperan que ella regrese. Quentin fue la última persona con la que sus padres la vieron cuando su padre la encontró en la casa de Quentin por la noche. Un investigador privado hace una pregunta sobre dónde pudo haber escapado Margo. Se da cuenta de un cartel de Woody Guthrie pegado a las persianas de su dormitorio. Cuando sus padres se fueron de casa, Quentin soborna a la hermana de Margo para que puedan investigar su habitación. El cartel los lleva a una canción llamada «La sobrina de Walt Whitman». La canción los lleva a un poema llamado «Canción de mí mismo», de Walt Whitman. En la habitación de Margo, hay una copia del poema con el texto resaltado. Un día, Quentin desquicia su puerta y encuentra otra pista: una dirección. Al día siguiente, Quentin y sus amigos faltan a la escuela y conducen hasta la dirección que dejó Margo. Cuando llegan, encuentran un centro comercial abandonado. En el interior, Margo dejó un mensaje pintado en las paredes. que dice: «Irás a las ciudades de papel y nunca volverás». Quentin cree que esta es la forma en que Margo confirma su suicidio, mientras que sus amigos creen que significa que estaba cansada de su vida falsa.
Quentin pasa un tiempo buscando más pistas sin éxito. El día de su graduación, mira el mapa de Nueva York que encontró en el centro comercial abandonado. El mapa tiene agujeros, uno de ellos en un lugar llamado Agloe, Nueva York. Busca a Agloe en Internet y descubre que Agloe es una trampa de derechos de autor, y que su población aumentó de cero a uno, hasta el 29 de mayo. Quentin, Ben, Lacey y Radar se saltan la graduación para ir a Nueva York a buscar a Margo. Como sabe que Margo cambió la población en el sitio, tienen que llegar a Agloe en menos de un día.
Cuando la pandilla llega a Agloe, Nueva York, encuentran a Margo viviendo en un granero. Margo se sorprende al verlos, ya que las pistas que dejó no estaban destinadas a encontrarla. Enojados por su reacción, Radar, Lacey y Ben abandonan el granero y se registran en un motel. Quentin se entera de que su visión de Margo era falsa, similar a la que ella había estado proyectando a todos los que conoció. Más tarde, Quentin le dice a Margo que estaba enojado porque ella lo hizo perder el tiempo. Margo le dice que realmente la salvó porque quería sentirse como el superhéroe que salva a la niña. Más tarde acepta que era obvio que no esperaba que Margo viviera la imagen que tenía de ella. Ambos dicen que se quieren y se besan. Más tarde, Margo le dice que la acompañe a Nueva York, pero Quentin le dice que tiene una vida en Orlando. Margo y Quentin se despiden por última vez y se prometen mantenerse en contacto.