Schon im Mittelalter lief der Verkehr durch die Innenstadt hauptsächlich über die Westernstraße. Sie mündet an ihrem östlichen Ende in den Marienplatz, den es seit 1784 gibt, als die hier erbaute Marktkirche St. Pankratius wegen Baufälligkeit abgerissen wurde. Die begehrte Lage um den nun freien Platz lockte vermögende Bürger, die hier ihre Häuser errichteten.
Im 16. Jahrhundert entstand das Heisingsche Haus. Bauherr war wahrscheinlich der Paderborner Bürgermeister Heinrich Stallmeister. Der Baumeister Franz Christoph Nagel gab dem Gebäude 1741 ein eindrucksvolles Portal im Stil des Barocks. 1835 kam es in den Besitz der Familie Heising. 1928 errichtete Dombaumeister Kurt Matern über dem ehemaligen Garten des Heisingschen Hauses das Eingangsgebäude für die ehemalige Städtische Sparkasse. Über dem mittleren Bogen ist weiterhin das Paderborner Stadtwappen sowie das Relief eines Pfennigs sichtbar.
Die Häuser um den Marienplatz sanken am 27. März 1945 in Schutt und Asche. Nur die Fronten des ausgebrannten Residenz-Theaters (im Westen), des Heisingschen Hauses, das rechte Nachbargebäude und das doppelflügelige Gitter im Eingangsbereich blieben erhalten. Die (Geschäfts-) Häuser Nr. 3/5 und 4/6 entstanden 1950/51 bzw. 1947/48 neu.
Das Erdgeschoss des Heisingschen Hauses wurde Ladenfläche, in die oberen Geschosse quartierte sich die Stadtverwaltung ein. Die ehemalige Schalterhalle wurde zum Einwohneramt. Nr. 2a beherbergte die Jugendbibliothek der Stadt Paderborn. Von Februar 1977 bis November 2022 war die Tourist Info Paderborn hier ansässig.
Der Marienplatz ist längst wieder ein beliebter Treffpunkt und Rastplatz für Bürger und Besucher. Er wird von Cafés, einer Eisdiele und einem Restaurant gesäumt, die bei schönem Wetter Tische und Stühle nach draußen stellen. Im Zentrum des Platzes erhebt sich seit 1861 die Mariensäule. Sie trägt eine Statue der Muttergottes. Ihr zu Füßen stehen die Heiligen Liborius und Meinolfus sowie die mittelalterlichen Kaiser und Könige Karl der Große und Heinrich II.
