Het eerste spoor van een gebedshuis op de plaats van de huidige Sint-Willibrorduskerk dateert uit 1264. Aanvankelijk was het een kapel die in 1304 werd verheven tot kerk.
Wellicht werd ze in de eerste helft van de 14de eeuw de eerste kapel (of kerk) vervangen door een nieuwe. Dit tweede gebedshuis deed slechts een eeuw dienst, want in 1454 werd er opnieuw een kerk gewijd, nu het derde bouwwerk, uitgerust met een torenspits van “honderd voet” hoogte.
Ongeveer een eeuw later, in 1542, drong Maarten van Rossum door tot in de Pothoek en Stuyvenberg. Hij hield zich er schuil in de Sint-Willibrorduskerk waardoor de kerk vanuit de stad werd bestookt en vernield.
Twee jaar na de feiten, op 15 juli 1544, werd de eerste steen gelegd van het vierde kerkgebouw. De nieuwe kerk werd zowat een jaar nadien ingewijd. Ook de toekomst van deze gebedsplaats was onzeker: op 5 augustus 1566 kwamen de beeldenstormers er op bezoek en op 2 maart 1579 werd de kerk in brand gestoken.
Dertig jaar later, op 13 mei 1613, werd ter vervanging van de uitgebrande kerk een tijdelijke houten kapel in gebruik genomen. In 1615 werd de vijfde kerk voltooid, maar in 1621, bij de afloop van de wapenstilstand van het Twaalfjarig Bestand, werd ze verlaten en verviel ze.
28 jaar later, op 20 december 1649, legde kanunnik Aubertus van den Eede de eerste steen voor een nieuw gebedshuis. Doordat de bevolking buiten de vroegere stadsmuren sterk uitbreidde, werd de Sint-Willibrorduskerk te klein en werden twee parochies afgesplitst: Sint-Jozef in 1860 en Sint-Amandus in 1864.
De kerkfabriek vatte rond die tijd het plan op om een nieuwe en grotere kerk te bouwen.
In 1887 werd de eerste spadesteek voor de bouw van de huidige kerk gegeven, volgens de plannen van de architecten Leonard & Hendrik Blomme. Op 23 september 1891 werd de Sint-Willibrorduskerk in haar huidige vorm ingewijd door kardinaal Petrus Lambertus Goossens. De kerk werd in 1976 beschermd als monument.
De kerk herbergt onder andere een schilderij van Peter Paul Rubens waarop Sint-Willibrordus de Heilige Familie aanbidt. Het schilderij werd in 1630 door een anonieme dame geschonken aan de parochie.
De naam Kerkstraat is relatief recent. De oude naam van deze straat is Eienstraat en verwees naar de Eiendijk. Dit was de dijk die op de weg van Deurne naar de stad ter hoogte van de vallei van de Potvliet tussen de Kroonstraat en de Provinciestraat. Het eerste gedeelte van de straat werd in 1846 als Kerkstraat gewettigd. In 1863 kwam er een tweede stuk bij aan de Kerkstraat.
Met de heraanleg van de Kerkstraat werd er voor de kerk een plein gecreëerd met daarop een mozaïek die een oosters tapijt uitbeeldt, verwijzend naar de diversiteit van de buurt. Dit plein is de gedroomde plek voor basketbal, rommelmarkten en activiteiten van wijkcomité Willibrordus zoals Kerkstraat Plage, Tango en het Warm Winters Wijkfeest.
De mozaïek is een sterk gestileerde versie van het profiel van de Sint Willibrorduskerk.