The most architecturally significant church in the area, St. Paul's combines a Neo-Romanesque body with twin towers in a late Renaissance style. With its stuccoed reinforced concrete walls, painted a brilliant white in a 1990 renovation project, and its tall towers topped by octagonal cupolas, the church can be seen from many points in Winnemucca. Above both towers rise louvered belfries topped by crosses. The church follows a cruciform plan, with a short transept and a curved apse projecting from the altar end of the nave. Above the main entrance a rose window admits light to the nave.
An influx of Italians and Basques in the late nineteenth and early twentieth centuries strengthened the Catholic community in Winnemucca. By 1926 Roman Catholics constituted the largest denomination in the state, according to the WPA Guide to Nevada. When the congregation decided to erect a large new church, it considered a style blending medieval Italian and Spanish Renaissance forms appropriate to display the size and aspirations of the local Catholic community. It also hired an out-of-state architect experienced in the design of churches—J. J. Foley of San Francisco. In the early twentieth century Catholic churches in the West often employed styles that evoked medieval and Counter-Reformation religious devotion. The monumental scale of the church also imparted legitimacy and longevity to a congregation that may have wished to counter the anti-Catholic sentiment widespread in the United States in the nineteenth and early twentieth centuries.