De Paulusbroedersluis is genoemd naar het Paulusbroederklooster, dat hier in de Middeleeuwen stond. In 1409 wordt het klooster voor het eerst genoemd, maar het bestond waarschijnlijk al langer. Je kunt het je misschien moeilijk voorstellen, maar in die tijd lag dit gebied buiten de stad. Om ruimte te houden voor alle monniken in het klooster, kocht het stukken grond aan de Kloveniersburgwal, Spinhuissteeg en Oude Hoogstraat. Uiteindelijk was dat hele stuk eigendom van het klooster. 

Maar in 1452 brak een brand uit in dit, toen nieuwe, deel van de stad. Een groot stuk van het klooster ging verloren. De Paulusbroeders bouwden een nieuwe kloosterkapel, maar niet lang daarna ging het minder goed met de kloosterorde. Het protestantisme kwam in opkomst en het klooster moest her en der stukken van hun eigendom verkopen om het hoofd boven water te houden. In 1578, tijdens de zogenaamde Alteratie, werd het katholieke stadsbestuur afgezet en de stad werd eigenaar van alle eigendommen van het klooster. De kapel werd verbouwd tot een kerk voor Waals Hervormde protestanten, die vanuit het zuiden naar Amsterdam vluchtten. Dat is nu de Waalse Kerk, hier vlakbij, aan de Oudezijds Achterburgwal.