Most bodies of our Solar System are "Frozen Worlds" where the prevailing surface temperature remains at or below freezing. On Earth there are vast permanently frozen regions of permafrost, polar ice sheets, and glaciers and the deep oceans and deep-sea marine sediments have remained at 2 - 4°C for eons. Psychrophilic and psychrotrophic microbiota that inhabit these regimes provide analogs for microbial life that might inhabit ice sheets and permafrost of Mars, comets, or the ice/water interfaces or sediments deep beneath the icy crusts of Europa, Callisto, or Ganymede. Cryopreserved micro-organisms can remain viable (in a deep anabiotic state) for millions of years frozen in permafrost and ice. Psychrophilic and psychrotrophic (cold-loving) microbes can carry out metabolic processes in water films and brine, acidic, or alkaline chanels in permafrost or ice at temperatures far below 0°C. These microbes of the cryosphere help define the thermal and temporal limits of life on Earth and may provide clues to where and how to search for evidence of life elsewhere in the Cosmos. Astrobiologists at the NASA Marshall Space Flight Center have collected microbial extremophiles from the Pleistocene ice wedges and frozen thermokarst ponds from the Fox Permafrost Tunnel of Alaska. Microbes have also been isolated from samples of Magellanic Penguin guano from Patagonia; deep-sea marine muds near hydrothermal vents; snow and permafrost from Siberia, and deep ice cores, ice-bubble and cryoconite rocks of the Central Antarctic Ice Sheet. These samples have yielded microbial extremophiles representing a wide variety of anaerobic bacteria and archaea. These microbes have been isolated, cultured, characterized and analyzed by phylogenetic and genomic methods. Images were obtained by Phase Contrast, Environmental, Field Emission Scanning and Transmission Electron Microscopes to study the ultra-microstructure and elemental distribution in the composition of these micro-organisms. We consider the Astrobiological significance of the Fox Tunnel with its rich assemblage of frozen microbes as proxy for developing techniques that may help optimize the search for evidence of life in the permafrost of Mars. We provide images of a novel anaerobic, heterotrophic, psychrotrophic bacterium (str.FTR1) isolated in pure culture from the Fox Tunnel. We also describe novel psychrotrophs isolated from guano of the Magellanic penguin (Spheniscus magellanicus) from the southern tip of Patagonia. These strains PmagG1 and PPP2) represent new species and genera of anaerobic microbes that grow at very low temperatures. The lowest limit for growth without morphological changes of str.PmagG1 is −4°C.