Gaden havde forskellige navne i 1500-tallet, f.eks. Vejerhusstræde, fordi den førte ned til vejerboden ved Gammel Strand.
Naboløs ligger i forlængelse af Hyskenstræde, som den tidligere var en del af.
I 1600-tallet kaldes den Naboløs Stræde og fra 1713 blot Naboløs.
Navnet skyldes formentlig, at der i gaden kun lå ét hus, der havde facade ud til den. Det var formentlig det nuværende Naboløs 4. De andre huse i gaden havde adresse på de omkringliggende gader, så helt naboløse var beboerne altså trods alt ikke.
En anden forklaring siges at være, at der i Naboløs boede en mand, der rengjorde og holdt opsyn med byens offentlige lokummer, der bl.a. lå i Magstræde. Den lugt, der fulgte med hans profession betød, at ingen ønskede at være nabo til ham.
Husene i Naboløs er alle opført kort efter den store brand i København i 1795, og de fleste bygget af murermester H. C. Ondrup. Alle gadens seks ejendomme er bygningsfredet.
I Naboløs 6, på hjørnet af Snaregade, ligger Henriette Melchiors Stiftelse.