The rheological properties of fibrin networks have been of long-standing interest. As such there is a wealth of studies of their shear and tensile responses, but their compressive behavior remains unexplored. Here, by characterization of the network structure with synchronous measurement of the fibrin storage and loss moduli at increasing degrees of compression, we show that the compressive behavior of fibrin networks is similar to that of cellular solids. A nonlinear stress-strain response of fibrin consists of three regimes: (1) an initial linear regime, in which most fibers are straight, (2) a plateau regime, in which more and more fibers buckle and collapse, and (3) a markedly nonlinear regime, in which network densification occurs by bending of buckled fibers and inter-fiber contacts. Importantly, the spatially non-uniform network deformation included formation of a moving "compression front" along the axis of strain, which segregated the fibrin network into compartments with different fiber densities and structure. The Young's modulus of the linear phase depends quadratically on the fibrin volume fraction while that in the densified phase depends cubically on it. The viscoelastic plateau regime corresponds to a mixture of these two phases in which the fractions of the two phases change during compression. We model this regime using a continuum theory of phase transitions and analytically predict the storage and loss moduli which are in good agreement with the experimental data. Our work shows that fibrin networks are a member of a broad class of natural cellular materials which includes cancellous bone, wood and cork.