Constellation Records est fondé en 1997 à Montréal par Ian Ilavsky, musicien du groupe Sofa, et Don Wilkie, qui se rencontrent en 1994 par des amis communs. Les deux hommes voulaient d’abord ouvrir une salle de concert légale, puis y adosser un label ; faute de lieu, ils organisent des soirées dans des appartements et des lofts, dont la série mensuelle Musique fragile dans leur loft du Vieux-Montréal, et collaborent avec les membres de Godspeed You! Black Emperor, avec qui ils organisent des concerts au Hotel2Tango, le loft où vivent certains d’entre eux. Les deux premières références sont des disques de Sofa ; la troisième est F♯ A♯ ∞ de Godspeed You! Black Emperor, tiré à cinq cents exemplaires en vinyle, dont les pochettes sont assemblées à la main et qui contient chacun un sou écrasé par un train du Mile End.

Le label s’est ensuite fait connaître avec Godspeed You! Black Emperor, A Silver Mt. Zion et Do Make Say Think, puis a élargi son catalogue sans se fixer sur un genre : post-rock, jazz d’avant-garde, folk, post-punk, électro-minimalisme et musique concrète. Des membres de Godspeed ont nourri d’autres projets du label, comme Black Ox Orkestar (klezmer) et Land of Kush ; le catalogue compte aussi Jerusalem in My Heart, Esmerine et des artistes venus d’ailleurs : Matana Roberts (Coin Coin Chapter Four: Memphis), Colin Stetson, Carla Bozulich, Vic Chesnutt, Fly Pan Am, Ought, Automatisme, Jessica Moss. La plupart des enregistrements ont lieu au Hotel2Tango, studio copropriété de membres de Godspeed et de Jerusalem in My Heart, installé dans un bâtiment partagé avec les bureaux du label.

Constellation compte environ 150 références en vingt-trois ans (début 2020). Il cultive une éthique de la production indépendante et des éditions soignées en vinyle, avec des pochettes sérigraphiées et des inserts, et reverse en 2020, pendant la pandémie, l’intégralité des recettes de sa boutique et de son Bandcamp à ses artistes. L’album Allelujah! Don’t Bend! Ascend! de Godspeed You! Black Emperor, publié par le label, remporte le prix Polaris en 2013.