Kirken er opkaldt efter den bibelske evangelist Matthæus.
Matthæus Kirke blev taget i brug i 1880 som den første kirke på Vesterbro. Den lå i den tidligste bebyggelse i på Vesterbro i kvarteret som er opstået langs Vesterbrogades sidegader og som gennemskæres af Matthæusgade.
Tidligere havde de få beboere der var på Vesterbro hørt til Frederiksberg Kirke.
Sognet blev efterhånden delt i en række sogne, Absalons, Elias, Maria, Getsemane, Apostel og Kristkirkens, hvor nye kirker opførtes.
Sankt Matthæus Kirke er tegnet af arkitekten Ludvig Fenger (1833-1905) og fik fra begyndelsen plads til 1.000 kirkegængere.
Byggestilen er inspireret af romanske kirker i Norditalien. Det var nødvendigt at pilotere grunden før byggeriet, fordi terrænnet var lavt og fugtigt.
Over indgangen mod øst hænger et relief udført af billedhuggeren Vilhelm Bissen (1836-1913), der forestiller de hellige tre konger.
Over prædikestolen er en Matthæusfigur, der er lavet af Th. Stein.
