Entró en servicio militar en 1884 y se graduó como oficial de la Marina Imperial Rusa en 1887.
También tomó parte en una expedición al golfo de Yeniséi dirigida por Leonid Dobrotvorski, que le dio experiencia en la navegación en aguas árticas.
Koloméitsev supervisó el equipamiento del Zaryá en el astillero de Colin Archer en Larvik, Noruega.
Pero Toll (más en consonancia con el espíritu de la época en Rusia) anhelaba la camaradería y trataba a los marineros comunes como iguales.
[1] Debido a las condiciones claustrofóbicas en el barco durante la primera invernada del Zaryá cerca de la isla Taymyr (un lugar que Toll bautizó como bahía Colin Archer (Bujta Kolin Árchera), en memoria del armador que preparó el Zaryá), los desacuerdos entre Toll y Koloméitsev se volvieron insalvables.
[2] Finalmente Toll recurrió a un procedimiento inusual y decidió enviar a Koloméitsev lejos, acompañado por el oficial cosaco Stepán Rastorgúyev, en un largo viaje por tierra en trineo con la misión de organizar depósitos de carbón para la nave en la isla Kotelny y en isla Dikson, así como llevar el correo de la expedición a Dudinka.
[4] Koloméitsev escribió dos libros acerca de su viaje con la Expedición Polar rusa, uno de ellos publicado en 1901 por la Academia Imperial Naval (Izvéstiya Imperátorskoy Akadémii Naúk) y el otro en 1902 por la Sociedad Geográfica Imperial (Izvéstiya Imperátorskago Rússkago Geografícheskago Óbschestva).
Se convirtió en un héroe en la batalla cuando trajo su barco junto al incendiado buque insignia, el Kniaz Suvórov.
Koloméitsev, también gravemente herido, fue capturado por los japoneses con las tripulaciones del Dmitri Donskói, Buiny y Oslabya en la isla Dajelet.
Sin embargo, después de la caída del movimiento Blanco en la guerra civil rusa, Koloméitsev fue al exilio con su esposa en Francia.