Black Star se formó a finales de los 90, bajo el sello Rawkus Records, un sello discográfico independiente de Nueva York.