En 1640 Dimitry Zyryan (también llamado Yarilo o Yerilo) fue por tierra al Indigirka. En 1641 navegó por el Indigirka, se dirigió al este y subió por el Alazeya. Aquí oyeron hablar de los Kolima y conocieron a los Chukchis por primera vez. En 1643 regresó al Indigirka, envió su yasak (tributo) a Yakutsk y regresó al Alazeya. En 1645 regresó al Lena, donde conoció a un grupo y se enteró de que había sido nombrado prikazchik (administrador de tierras) del Kolima. Regresó al este y murió a principios de 1646. En el invierno de 1641-42, Mijaíl Stadukhin, acompañado por Semión Dezhniov, fue por tierra a la alta Indigirka. Pasó el invierno siguiente allí, construyó barcos y navegó por el Indigirka hacia el este hasta el Alazeya, donde se encontró con Zyryan. Zyryan y Dezhniov se quedaron en el Alazeya, mientras que Stadukhin se fue al este, llegando al Kolima en el verano de 1644. Construyeron una zimovye (cabaña de invierno), probablemente en Srednekolymsk, y regresaron a Yakutsk a finales de 1645.
En 1892-94 el barón Eduard Von Toll llevó a cabo estudios geológicos en la cuenca del Kolima (entre otros ríos siberianos del Lejano Oriente) en nombre de la Academia Rusa de Ciencias (Barr, 1980). Durante un año y dos días, la expedición recorrió 25.000 kilómetros (16.000 millas), de los cuales 4.200 kilómetros (2.600 millas) eran ríos, llevando a cabo estudios geodésicos en ruta.
El Kolima es conocido por sus campos de trabajo Gulag y la minería de oro, ambos de los cuales han sido ampliamente documentados desde que se abrieron los archivos soviéticos de la era de Iósif Stalin. El río da título a una famosa antología sobre la vida en los campos de Gulag de Varlam Shalamov, Los Cuentos de Kolima.
Después del cierre de los campamentos, los subsidios estatales, las industrias locales y las comunicaciones se redujeron a casi nada. Muchas personas han emigrado, pero los que permanecen en la zona se ganan la vida pescando y cazando. En pequeños asentamientos de pescadores, los peces a veces se almacenan en cuevas talladas en permafrost. Los últimos estadounidenses en visitar el Kolima durante la era soviética, antes de la perestroika, fueron la tripulación de la goleta de vela Nanuk en agosto de 1929, cuya visita fue capturada en una película tomada por la hija de 18 años del propietario del Nanuk, Marion Swenson. Los dos primeros estadounidenses en visitar el Kolima después de la visita del Nanuk fueron el escritor Wallace Kaufman y la periodista Rebecca Clay, que viajaron en cutter de Ziryanka a Cabo Verde en agosto de 1991.En febrero de 2012, las Actas de la Academia Nacional de Ciencias informaron que los científicos habían cultivado plantas de fruta Silene stenophylla de 30.000 años de antigüedad, que se almacenaba en madrigueras de ardillas cerca de las orillas del río Kolima y se conservaba en permafrost.
