The Khyber Building was originally called the Church of England Institute and was built in 1888. Its architect, Henry Frederick Busch, was considered one of the eminent architects of the time. He designed this unique building which is described by historian Elizabeth Pacey as a "highly decorative Gothic composition" in the "ornate Victorian style".

In the 70s, a cafe called "The Khyber Cafe" was operated on the ground floor. The name seemed to stick with Haligonians and since then, the building has been referred to as "the Khyber Building" even though there have been numerous other businesses in the building over the years.