Subsurface solute transport under surface warming and degrading permafrost conditions is studied using a physically based model of coupled cryotic and hydrogeological flow processes combined with a particle tracking method. Changes in the subsurface water and inert solute pathways and travel times are analyzed for different modeled geological configurations. For all simulated cases, the minimum and mean travel times increase nonlinearly with warming irrespective of geological configuration and heterogeneity structure. The timing of the start of increase in travel time depends on heterogeneity structure, combined with the rate of permafrost degradation that also depends on material thermal and hydrogeological properties. The travel time changes depend on combined warming effects of: i) increase in pathway length due to deepening of the active layer, ii) reduced transport velocities due to a shift from horizontal saturated groundwater flow near the surface to vertical water percolation deeper into the subsurface, and iii) pathway length increase and temporary immobilization caused by cryosuction-induced seasonal freeze cycles.