1973-2005: Storgata 118
Biblioteket flyttet i 1973 til Storgata 118, som egentlig var ment å være en midlertidig løsning. I Storgata 118 fikk biblioteket barneavdeling og edb-plan.
Midlertidige lokaler og barnebibliotek
I 1973 flyttet biblioteket atter en gang, da inn i Storgata 118 i Odd Fellows nyoppførte bygg. Løsningen var ment å være midlertidig, men her endte biblioteket opp med å være i over 30 år. I sine nye lokaler kunne biblioteket endelig åpne en egen barneavdeling, noe som hadde vært ønsket og jobbet med siden 1950-tallet.
Digitalt bibliotek
På 1990-tallet begynte digitaliseringen av biblioteket for alvor. I 1991 utarbeidet biblioteket en edb-plan, og samme år gikk biblioteket sammen med Troms fylkesbibliotek til anskaffelse av biblioteksystemet Bibliofil. I 1996 var 70 % av bibliotekets samling registrert i systemet. Tromsø bibliotek ble innvilget medlemskap i Uninett i 1995, og kunne året etter tilby gratis internettilgang.
Hvor skal biblioteket være?
Behovet for egnede lokaler for biblioteket ble etter hvert stort. Formannskapet bestemte i 1984 at det skulle vurderes nye lokaler til biblioteket i forbindelse med bygging av nytt rådhus. I september 1986 vedtok kommunestyret at nytt rådhus og bibliotek skulle plasseres på seminartomta ved Fr. Nansens plass. Planen ble stoppet i kommunestyremøte i mai 1989, og ble aldri noe av. Det ble også vurdert å ombygge Strandtorget 2B til eldresenter og bibliotek, men heller ikke dette gikk gjennom. I 1991 kunne Tromsø bibliotek feire 120-årsjubileum, fremdeles i sine «midlertidige» lokaler.