The conventional view holds that girih (geometric star-and-polygon, or strapwork) patterns in medieval Islamic architecture were conceived by their designers as a network of zigzagging lines, where the lines were drafted directly with a straightedge and a compass. We show that by 1200 C.E. a conceptual breakthrough occurred in which girih patterns were reconceived as tessellations of a special set of equilateral polygons ("girih tiles") decorated with lines. These tiles enabled the creation of increasingly complex periodic girih patterns, and by the 15th century, the tessellation approach was combined with self-similar transformations to construct nearly perfect quasi-crystalline Penrose patterns, five centuries before their discovery in the West.