De Gelderse Oorlogen (1502-1543) zijn een reeks conflicten tussen voornamelijk Holland, Vlaanderen en Brabant onder leiding van de Habsburgse vorsten en Gelre, Groningen en de Ommelanden en Friesland, onder leiding van Karel van Gelre. Toen Graaf Karel van Gelre in 1508 Weesp en Muiden bezette, werd uit voorzorg de Lastage door hem volledig platgebrand. In 1512 werd de Lastage voor de tweede keer platgebrand, nu door Gelderse troepen. De stadsregering ging nu toch over tot een vorm van bescherming. Aan de oostkant van de Lastage werd een nieuwe gracht gegraven, de huidige Oudeschans en in 1516 werd, waar deze gracht het IJ naderde, een uitkijktoren gebouwd. Deze toren bood uitzicht over de Zuiderzee. De bewoners en ondernemers op Lastage konden zo eerder gewaarschuwd worden. Niet ideaal maar beter dan niets.

De uitkijktoren krijgt de naam van Monte-Albaens-tooren. In de ‘Historische Beschrijving der Stadt Amsterdam’ van Olfert Dapper (1663) wordt verklaard dat de naam is ontstaan door bouwplannen van Hertog van Alva (Alba) die bij de toren een kasteel wilde stichten met de naam Monte Albano. In de volksmond verbasterde dit al snel tot Montelbaanstoren.
Jan Wagenaar is het hier niet mee eens en komt met een heel andere theorie. Die gaat terug aar het populaire middeleeuwse verhaal over de Vier Heemskinderen. In dit verhaal nemen de Vier Heemskinderen en hun magische ros Beiaard het op tegen de machtige Keizer Karel de Grote. Dit verhaal was zó populair dat vele huizen in Amsterdam nog gevelstenen hebben die een deel van het verhaal vertellen. Eén van die Vier Heemskinderen was Reinout van Montalbaen. Hij zou op een rots in Zuid-Frankrijk het kasteel Montauban hebben gebouwd.
Hoe het zij, sinds 1537 wordt de naam Montelbaanstoren gebruikt.

Met de aanleg van de bolwerken van de Tweede Uitleg verloor de toren in 1591 zijn functie. Een nieuwe functie als wachthuis en magazijn breekt aan. In 1606 ontwierp Stadsbouwmeester Hendrick de Keyser een bekroning in renaissancestijl voor een uurwerk en enkele luidklokken. De achthoekige bakstenen opbouw die nu op de oude ronde torenromp staat en de torenspits dateren uit deze tijd. De toren bereikte hiermee een hoogte van 48 meter. Aan deze klokken dankt de Montelbaanstoren nu weer zijn bijnaam ‘Malle Jaap’, de klokken begonnen namelijk regelmatig spontaan te spelen waarna ze soms weer dagenlang stil bleven. De reden hiervoor was de verzakking van de toren.
De toren was bij de bouw gefundeerd op plaggen. In 1610 dreigde de toren door het toegenomen gewicht hiervan af te glijden en zakte scheef. Met veel touwwerk werd de toren weer rechtgetrokken waarna een nieuwe stenen fundering werd aangebracht.

In 1852 dreigde sloop, maar een financiële meevaller redde de Montelbaanstoren. Vanaf 1878 kreeg het Stadswaterkantoor hier zijn kantoor. In 2006 was deze dienst inmiddels de afdeling Uitvoering van de sector Waterbeheer van de dienst Riolering en Waterhuishouding geheten en verliet de toren. Er volgde een grondige restauratie. Vanwege de torenhoge huurprijs stond het gebouw hierna enige jaren leeg. Van 2010 tot 2013 werd het gebouw voor een veel lager bedrag verhuurd aan de Stichting Secret Garden, een belangenorganisatie die zich inzet voor homofiele mensen van buitenlandse afkomst. Sinds 2014 is het kantoor van Private Boat Tours in de toren gevestigd (2025).
We gaan nog even terug naar de tijd van de Tachtigjarige Oorlog. In de toren zou zich een gezin hebben verstopt om te ontkomen aan de Spaanse vijand. Helaas werden zij op 2 juni ontdekt en vermoord in de Montelbaanstoren. Zij zouden elk jaar op 2 juni in de toren komen spoken om hun vreselijke laatste momenten te herbeleven.