The Khyber was an initially established by Bill Roberts with a group of young artists called the No Money Down Cultural Society in 1994. Bill Roberts, a photographer and arts administrator, noticed that the building, owned by the City of Halifax, had been emptied out of all tenants and negotiated with the city to take care of the building in exchange for being able to hold exhibitions and operate a dance club. No Money Down was paying rent on a month-to-month basis. An informal strategy was used to run a gallery, called Khyber Space for Art and the Khyber Café - a venue for live entertainment and the society's only fundraising apparatus.

In March 1995, a new society was established that introduced a more formal administrative structure to manage the growing complexities of the project. This included launching a wide-spread public and political campaign directed towards the Halifax Regional Municipality (the building's landlord) to secure a long-term lease for the building. The society, involving some of the same individuals from No Money Down, was incorporated on March 10, 1995 as the Khyber Arts Society.

Although the city had placed the building on the market, a media campaign was launched to get public support for the Khyber and with the help and mentorship of the Heritage Trust of Nova Scotia a lobbying campaign with city councillors was also launched.

The cafe and galleries were managed on a volunteer basis for the majority of 1995 and the centre did not need to apply for government funding (although they were not able to pay artist fees). Two full-time staff were finally hired in the Fall '95 - a Cafe Manager/Bartender (Kelly Mark) and an Administrative Director (Caroline Chan). The majority of income at this time came from licensed events using Special Occasion Licenses and all ages raves. The ultimate goal of operating a permanently licensed bar was still unattainable because the society did not have a lease.

Even with the support of several aldermen on Halifax City Council and the promise of a 3-year lease at $1 a year that was to begin in June 1995, it became clear that the impact of the adjoining Neptune Theatre's expansion would require a re-negotiation of the lease and relocation of the Khyber to facilitate extensive structural renovations to the Khyber building. Due to these complications the city did not formalize the $1/year lease which was promised.

The Khyber's structural renovations took place from November 1996 to November 1997. The centre was provided with a temporary gallery space on Portland Place where it presented a full year of programming and offered its Khyber Kids summer art program for the first time. During this time a new five-year renewable lease, restoration plan and business plan were negotiated, giving the Khyber reduced rent in the first four years in exchange for providing ongoing volunteer labour to restore the building. During this phase of city renovations, the centre decided to renovate the cafe and prepare it to apply for a permanent liquor license. The Khyber obtained a loan from Heritage Trust of Nova Scotia (a non-profit advocacy group for heritage preservation who occupy a 1st floor office in the building) and fundraised for more money to self-finance the renovations and to purchase bar equipment. The Khyber Club opened in March 1998.

In 1998 CARFAC NOVA SCOTIA established a shared office space with the Khyber. The Khyber Club quickly established itself as a regular meeting place for visual artists and an important venue for Halifax's emerging music scene.

Emily Vey Duke, the current Artistic Director, was hired in May 2004.