Purpose: Animal studies have shown that recent musculoskeletal injuries increase the risk of decompression sickness (DCS). However, to date no similar experimental study has been performed in humans. The aim was to investigate if exercise-induced muscle damage (EIMD)—as provoked by eccentric work and characterized by reduced strength and delayed-onset muscle soreness (DOMS)—leads to increased formation of venous gas emboli (VGE) during subsequent hypobaric exposure. Methods: Each subject (n = 13) was on two occasions exposed to a simulated altitude of 24,000 ft for 90 min, whilst breathing oxygen. Twenty-four hours prior to one of the altitude exposures, each subject performed 15 min of eccentric arm-crank exercise. Markers of EIMD were reduction in isometric m. biceps brachii strength and DOMS as assessed on the Borg CR10 pain scale. The presence of VGE was measured in the right cardiac ventricle using ultrasound, with measurements performed at rest and after three leg kicks and three arm flexions. The degree of VGE was evaluated using the six-graded Eftedal–Brubakk scale and the Kisman integrated severity score (KISS). Results: Eccentric exercise induced DOMS (median 6.5), reduced the biceps brachii strength (from 230 ± 62 N to 151 ± 8.8 N) and increased the mean KISS at 24,000 ft, both at rest (from 1.2 ± 2.3 to 6.9 ± 9.2, p = 0.01) and after arm flexions (from 3.8 ± 6.2 to 15.5 ± 17.3, p = 0.029). Conclusion: EIMD, induced by eccentric work, provokes release of VGE in response to acute decompression.