Durch die Entwicklung der Stadt Sindelfingen und das Anwachsen der Katholikenzahl war es notwendig geworden, im Norden der Stadt eine weitere Kirche zu errichten. Ursprünglich einmal in den Pfarrwiesen geplant, entschied man sich schließlich, die Kirche in dem neuen, sich rasch ausdehnenden Siedlungsgebiet Eichholz zu erbauen.
1968 erfolgte durch Pater Huwyler der erste Spatenstich und bereits am 1.Advent 1970 fand die feierliche Einweihung der Kirche St. Paulus durch Bischof Leiprecht statt. Das zugehörige und gerne genutzte Gemeindehaus wurde 1973 fertig gestellt. 1974 wurde St. Paulus zur selbstständigen Pfarrei erhoben, später aber 2005 auf Empfehlung des Kirchengemeinderats und anschließender Entscheidung des Bischofs zurück zur gemeinschaftlichen Pfarrei mit St. Joseph gegegeben. | 
 |
Der Marienaltar in St. Paulus wurde durch Gisela Bähr aus Pforzheim gestaltet, die auch die in ihrer Schlichtheit beeindruckende Altaranlage, die den Gedanken des gemeinsamen Tisches aufgreift, entworfen hat. |  |