Memorias del hielo tiene lugar simultáneamente con los eventos de Las puertas de la Casa de la Muerte, comenzando aproximadamente cuatro meses después de los eventos de Los jardines de la Luna. El segundo ejército de Dujek supuestamente se vuelve renegado, con Whiskeyjack como segundo al mando, para unirse a Anomander Rake y Caladan Brood para atacar al Dominio Painita, un imperio caníbal y destructivo dirigido por el Vidente Painita, un jaghut. El clan de las Caras Blancas de los barghastianos también se unen a la contienda después de que el soldado malazanon Trote se demuestra en combate individual en contra del hijo de un jefe del clan. Los otros hijos del jefe del clan descubren que los barghastianos descienden de aquellos T'lan Imass que no se unieron al ritual del Tellann y liberaron a sus dioses de Capustan.
La primera gran batalla es en Capustan, donde las Espadas Grises adoradoras del dios Fener evitan la peor parte del asalto hasta que Dujek y su compañía llegan. El Yunque del escudo Anvil Itkovian toma el sufrimiento de decenas de miles de muertos sobre sí mismo, a pesar de que Fener ya no está accesible (acaban de acontecer los eventos en Las puertas de la Casa de la Muerte) para aliviarlo, y las Espadas Grises recurren a los otros dioses de guerra por nuevo patrocinio (Togg y Fanderay). El escolta de caravana Rezongo se convierte en la Espada Mortal de Treach cuando su amiga Piedra es violada y golpeada en Capustan, y se une a la campaña contra el Painita.
Toc el Joven, que desapareció durante los Jardines de la Luna, emerge de la senda del caos a través de una escisión cerca de Alborada con el dios ancestral Togg presente en su consciencia y ocasionalmente poseyéndolo. Se encuentra con Onos T'oolan, la hija de Draconus, Lady Envidia, y sus mascotas, uno de los cuales tiene presente al dios ancestral y al amante perdido de Togg, Fanderay, y sus esclavos, los guerreros Seguleh. El grupo de Lady Envidia ataca al Dominio Painita desde un flanco diferente y conduce al Vidente a Coral, aunque no antes de que Toc se infiltre en el Dominio y sea capturado y torturado por el Vidente.
Los Abrasapuentes llegan primero a Coral y se abren camino hacia la ciudad con la ayuda de los morantianos, mientras que Ben el rápido, con el shaman bargastiano Talamandas (a quien rescata de una trampa espiritual) y el apoyo de Hood, evade el envenenamiento del Vidente Painita para atraparlo. Whiskeyjack desaparece en combate cuando Kallor, quien como emperador decenas de miles de años atrás mató a la población de un continente en lugar de dejarlos rebelarse (los cuerpos ahora forman la senda imperial), traiciona el ataque cuando se le prometió la posición de rey en la nueva Casa de las Cadenas del dios Tullido, que patrocina al Painita por detrás de escena. Anomander Rake sumerge a Engendro de Luna en el océano frente a Coral para acercarse sigilosamente y aplastar el reducto del Painita al final.
La Mhybe, madre de Zorraplateada, renacida de Velajada, Bellurdan y Escalofríos, envejece rápidamente y quiere suicidarse cuando Zorraplateada parece no amarla, pero Kruppe la convence de que se reconcilien al final después de que Zorraplateada, con la ayuda de Kruppe prepara la senda de Tellann, sembrada con fertilidad por los recuerdos de Itkovian del dolor de los T'lan Imass que se reúnen a la llamada de Zorraplateada para recibir a Togg y Fanderay como señores de la Bestia.
El Vidente Painita resultó haber sido conducido a la locura y la venganza loca por el confinamiento de él y su hermana cuando fue ocultado por la hermana de Tool, Kilava, en la escisión de Alborada para protegerlos del genocidio intencionado de los jaghut por Pran Chole cientos de miles de años atrás. El Vidente usa a la matrona K'Chain Che'Malle, que fue liberada de la escisión cuando él y su hermana fueron puestos allí, para torturar a Toc y generar soldados K'Chain. Cuando Paran como Maestro de la Baraja elige la misericordia, Ben el rápido ayuda a liberar a la hermana del vidente de la escisión. El Vidente luego coopera en el uso de su hielo de la senda Omtose Phellack para frenar el envenenamiento de Burn por el dios Tullido. Por devolverle a Fanderay, Togg pone el alma de Toc en el cuerpo sin alma del sirviente Anaster del vidente y restaura la mortalidad y la carne de Tool.
El Engendro de Luna termina muy dañado durante el ataque contra el Dominio Painita, y los Abrasapuentes caídos, junto con el líder del Morantianos negros, son trasladados para descansar dentro de la fortaleza. Los restantes Abrasapuentes (incluido Paran, que con la ayuda de Dujek figura entre las víctimas) se retiran a Darujhistan para abrir un bar, donde el epílogo les muestra escuchando al historiador Imperial Duiker contar la historia de la «Cadena de Perros».
Las tramas secundarias involucran a los irregulares de Mott, la nigromancia de Bauchelain y Korbal Espita y las repetidas borracheras de Ben el rápido y los Abrasapuentes. El amor naciente entre Whiskeyjack y la Tiste Andii Korlat, y los enfrentamientos para probar su destreza entre los Seguleh y Tool que tienen que ser disuadidos repetidamente por Lady Envidia.
