En el espacio donde estuvo parte del cementerio musulmán, comienza a formarse esta plaza a principios del siglo XVI, en tierras de la Orden de Calatrava y en ella se vendían cereales, legumbres y tocino. Ya tiene este nombre en el XVII que ocupaba prácticamente el mismo espacio que hoy. A veces, más que a la plaza en su conjunto, se hacía referencia a las aceras: aceras del Contador Mena, de doña Marta, de los Madereros o de la Hospedería. D’Aulnoy, en el viaje que hizo por España en 1676 dice que esta plaza es una de las más importantes en cuanto al comercio madrileño. A mediados del XVIII se construye una nueva manzana, a la izquierda de la calle del Humilladero donde se levantaba la iglesia de Nuestra Señora de Gracia, reduciéndose el espacio de la plaza. Esta manzana desaparece a principios del siglo XX siendo ocupada primero por barracones del mercado y después por el nuevo mercado.
En 1622 esta plaza se adornó instalando un jardín con motivo de las fiestas de canonización de San Isidro. Desde 1815 al 1835 era el lugar donde se ejecutaba a los reos como el general Riego. Ahorcado aquí en 1823 pero no así al famoso bandido Luis Candelas, que aunque muchos autores dicen que se le dio garrote vil en esta plaza, donde realmente se le ejecutó fue en la Puerta de Toledo al lado de Pontones. Después de la Revolución de 1868, y durante un breve periodo de tiempo, se llamó plaza de Riego, en honor al general ajusticiado aquí.
A Galdós esta plaza le parecía pobre, sucia y desangelada.
«La plazuela de la Cebada, prescindiendo del mercado que hoy la ocupa desfigurándola y escondiendo su fealdad, no ha variado cosa alguna desde 1823. Entonces, como hoy, tenía aquel aire villanesco y zafio que la hace tan antipática, el mismo ambiente malsano, la misma arquitectura irregular y ramplona. Aunque parezca extraño, entonces las casas eran tan vetustas como ahora, pues indudablemente aquel amasijo de tapias agujereadas no ha sido nuevo nunca. La iglesia de Nuestra Señora de Gracia, viuda de San Millán desde 1868, tenía el mismo aspecto de almacén abandonado, mientras su consorte, arrinconado entre las callejuelas de las Maldonadas y San Millán, parecía pedir con suplicante modo que le quitaran de en medio. La fundación de doña Beatriz Galindo no daba a la plaza sino podridos aleros, tuertos y llorosos ventanucos, medianerías cojas y covachas miserables. La elegante cúpulas de la capilla de San Isidro, elevándose en segundo término, era el único placer de los ojos en tan feo y triste sitio.
Texto incluido en nuesta novedad ‘Barrio de La Latina, su historia, sus calles y sus gentes de paso‘