Denne kirke afslutter en periode med 110 års kirkebyggeri i Herning - 6 kirker opførtes i de to oprindelige sogne og kirken opnåede tilmed, at blive den nyeste i Danmark inden århundredeskiftet.

I perioden med udbygningen af Gullestrup i Hernings nordlige del med et stort boligområde omfattende leje- og parcelhusbebyggelse fremkom ønsket om en sognekirke i 1970´erne hvor bydelen og udflytningen øgedes. 

En vandrekirke - en pavillon i træ opstilledes og fra 1981 afholdtes gudstjeneste her. Fra 1992 udskiltes sognet fra Herning og byggeplanerne tog form med en endelig vedtagelse i 1995. Kirkens grundsten blev lagt i november 1997 og indvielsen foregik 3. s. i advent 1998.

Gullestrup kirke, er opført i teglsten og fremtræder med vandskurede vægge ude og inde. Kirkens skib er uden loft og har en højde på 14 meter. Rummet får lysindgang fra fire store vinduer under taget.

I sydvæggen er placeret en række glasmalerier langs med kirkebænkene. Glasmaleren Hans Berg har her fremstillet påskeugens forløb. Døbefont og alterbord er hugget i svensk granit.