In the 1920s, African Americans formed several chapters of the Knights of Pythias in Pittsburgh. A group of construction workers belonging to Union Local 111 commissioned Louis Bellinger, Pittsburgh's first African American architect of prominence, to design its lodge house. Born in South Carolina in 1891, Bellinger graduated from Howard University in 1914.

At first, the building flourished, with a dining hall on the first floor, a ballroom on the second, and offices on the third; but a downturn in economic conditions forced the sale of the temple in the 1930s to Pittsburgh theater impresario Harry Hendel. Having owned and lost an earlier Granada Theater, Hendel transferred its name to this building. The temple's dining hall became a theater, usually showing Yiddish movies, while the second floor housed the Savoy Ballroom, named for still another of Hendel's earlier businesses.

Bellinger's original design set three stories of windows in yellow brick below a cornice consisting of squared notches over a frieze of oval terra-cotta tiles. In 1937, Alfred M. Marks (1891–1970) added shimmering red, blue, and yellow glazed enamel panels to the ground floor. The marquee combines designs in blue, yellow, green, and red. The refurbished New Granada Theater remained the glory of the Hill for another three decades, hosting all the giants of the Jazz era: Count Basie, Cab Calloway, Ella Fitzgerald, Lionel Hampton, and Lena Home. The New Granada closed after riots ripped through the Hill in the late 1960s. The Hill Community Development Corporation plans to rehabilitate it as part of Granada Square, a hub of educational, social, and artistic activities for the revived Hill of the future.