We investigated the characteristics of extracellular matrix (ECM) in the soft tissue of two frozen baby woolly mammoths (Mammuthus primigenius) that died and were buried in Siberian permafrost approximately 40,000 years ago. Morphological and biochemical analyses of mammoth lung and liver demonstrated that those soft tissues were preserved at the gross anatomical and histological levels. The ultrastructure of ECM components, namely a fibrillar structure with a collagen-characteristic pattern of cross-striation, was clearly visible with transmission and scanning electron microscopy. Type I and type IV collagens were detected by immunohistochemical observation. Quantitative amino acid analysis of liver and lung tissues of the baby mammoths indicated that collagenous protein is selectively preserved in these tissues as a main protein. Type I and type III collagens were detected as major components by means of liquid chromatography–mass spectrometry analysis after digestion with trypsin. These results indicate that the triple helical collagen molecule, which is resistant to proteinase digestion, has been preserved in the soft tissues of these frozen mammoths for 40,000 years.