As the Catholic population of Dubuque increased, Archbishop James J. Keane saw the need to establish a new parish in September 1922. The Church of the Nativity is located on Alta Vista Street with Rev. Henry P. Rohlman as the founding pastor. Father Rohlman consulted architect Casimir Krajewski. They planned a church and school in English-Gothic style. Archbishop Keane blessed the cornerstone on July 4, 1923, and dedicated the new church on December 23. The parish has moved through three worship sites: the first was a temporary site in the old school building; the second was a new church begun in 1926, and dedicated on November 20, 1927; the third is the present church begun in 1965, and dedicated in December 1967. 

Nativity Parish operated an elementary school from 1924 to 2001 at which time the school became part of Holy Family Catholic Schools. The elementary school remained on site until the spring on 2005. Nativity Parish hosted the Holy Family Middle School from 2005-2006, while the new middle school was being built. The Sisters of the Visitation staffed the school from 1924 until the fall of 1989. 

After Father Rohlman's appointment as bishop of Davenport, Rev. Michael L. Kerper became the second pastor of Nativity and served from July 1927, until his death in 1957. Since then many priests have served as pastors and associate pastors. At least 33 women and three men from the parish entered religious life and 21 men have been ordained priests. In the 1990s a sister parish relationship was established between Nativity and the Diocese of Bellary, India.

At the present time, Nativity Parish is involved with pastoral planning in several ways. From 2008-2010, the parish conducted a capital campaign and installed a new hybrid geothermal heating and cooling system which serves the church, religious education building and office building. Members of the parish participated in the Dubuque deanery pastoral planning process from 2009-2010. After the closing of St. Mary Parish, new members were welcomed to Nativity. In 2011, Nativity Parish began establishing a new strategic plan for the future.

Recently Nativity Parish has been celebrating their 90th anniversary. It was 90 years ago, on December 23, 1923, that the first Mass was celebrated in the first of the three church buildings (the first was part of the the so-called "Old School" (used for the first two years), the second was what is now called Upper Kerper Hall, and the third is the current church, the "New Church."). The first Mass was celebrated by the Archbishop of Dubuque, James J. Keane, with the presence of the first pastor, the future Archbishop Henry P. Rohlman, as well as the ancestors of many current parishioners. One person that was present for the 90th anniversary of the dedication of the cornerstone of the church building in July had attended Mass in the first church building.