The Lyme disease spirochete Borrelia burgdorferi exists in nature in an enzootic cycle that involves the arthropod vector Ixodes scapularis and mammalian reservoirs. To disseminate within and between these hosts, spirochetes must migrate through complex, polymeric environments such as the basement membrane of the tick midgut and the dermis of the mammal. To date, most research on the motility of B. burgdorferi has been done in media that do not resemble the tissue milieus that B. burgdorferi encounter in vivo. Here we show that the motility of Borrelia in gelatin matrices in vitro resembles the pathogen's movements in the chronically infected mouse dermis imaged by intravital microscopy. More specifically, B. burgdorferi motility in mouse dermis and gelatin is heterogeneous, with the bacteria transitioning between at least three different motility states that depend on transient adhesions to the matrix. We also show that B. burgdorferi is able to penetrate matrices with pore sizes much smaller than the diameter of the bacterium. We find a complex relationship between the swimming behavior of B. burgdorferi and the rheological properties of the gelatin, which cannot be accounted for by recent theoretical predictions for microorganism swimming in gels. Our results also emphasize the importance of considering borrelial adhesion as a dynamic rather than a static process.