The objective of this research was to determine the effect of exopolysaccharide (EPS) production by lactic acid bacteria on the microstructure and rheology of Karish cheese, a soft acid coagulated cheese made using skim milk. An EPS-producing strain of Streptococcus thermophilus, and its EPS non-producing genetic variant were used to make comparable batches of the cheese. EPS in cheese was visualized by cryo-SEM as a large, dense, filamentous mass. Cheese made with the EPS non-producing culture was characterized by a dense protein network with smaller pores compared to that prepared with the EPS-producing culture. High elastic and viscous moduli measured by dynamic rheology were observed for EPS negative cheese and was attributed to its dense protein network. Creep test experiments demonstrated that cheese prepared with the EPS non-producing strain was more rigid and recovered its deformation, while cheese made using the EPS producing culture was more deformable. These results indicate that EPS-producing cultures can improve the physical properties of Karish cheese by reducing undesirable rigidity.