Kompagnistræde lå i middelalderen sammen med Farvergade og Læderstræde helt ud til stranden.
Gaden var oprindeligt en del af Ladbrostræde (det tidligere navn for Læderstræde), men er senere blevet opkaldt efter et hus, der tilhørte Danske Kompagni, der blev oprettet 1443.
Danske Kompagni var et laug, der var dannet af de danske købmænd i København. Lauget var et modstykke til de tyske købmænds Tyske Kompagni,.
Laugshuset havde en stor have, hvor der blev holdt skydekonkurrencer, og lauget ændredes efterhånden til et skydeselskab, hvor både adelsfolk, kongelige og sågar kvinder kunne være medlemmer. Der blev skudt til måls efter en kunstig fugl på en stang og vinderen blev fuglekonge.
I starten skød man med buer og armbrøster, men efterhånden gik man over til bøsser. Fuglen var formet som en papegøje, og derfor siger man om en vinder, at han har ”skudt papegøjen”. Papegøjemesteren, som vinderen hed, skulle give seks tønder øl, og desuden hele det næste år give en omgang, når han mødte gildebrødrene i byens vinkælder.
I 1500-tallet flyttede papegøjeskydningen til Vesterbro omkring den nuværende Skydebanegade, og i 1700-tallet opførtes der derude en fornem bygning til selskabet.
