As the world's leading classical record label, Naxos is arguably Hong Kong's best kept secret. Music lovers are always surprised to learn that this household name, based in Cyberport, was conceived and developed in our very own city, a pin-prick on the international music scene and more famed for a love of money than devotion to Mozart. Having notched up 25 years of making classical music accessible to the masses, however, the company can look back with considerable satisfaction on its David-and-Goliath success story - one shot through with staggering statistics, the occasional prophetic moment and even a touch of the miraculous.

Exercising his grip on both the central core and the innovative edge of the Naxos empire throughout that quarter of a century has been Klaus Heymann: 76 years young [sic], dapper, sporty and one of the most courteous subjects one might hope to interview. He's also someone whose laser-beam eye for detail you would never want to underestimate, as one British writer found to his cost following litigation over a false statement he published in a book. ("A very careless journalist; he doesn't take notes.")

Heymann doesn't play an instrument, nor can he read music, which suggests the opposites-attract principle was at play when he fell in love with renowned Japanese violinist Takako Nishizaki, on August 13, 1974. ("That's the day we celebrate, not our wedding.") His wife of 37 years has no executive position within the company but whispers in his ear from time to time on artistic matters. In the early days of Naxos, when Heymann was on the hunt for good, cost-effective musicians who were prepared to take a leap of faith with his new, budget-label recordings, Nishizaki was often signed up. ("She was my wife; she had no choice.") Now one of the most frequently recorded and best-selling violinists ever, her renown as a soloist is complemented by her reputation as a teacher, strengthening the bond with her husband in his crusade to maintain education as a core element of the Naxos business model. ("If we want to grow, we have to educate our market.")

BORN IN FRANKFURT in 1936, Heymann studied English and the Romance languages, first at his local university, then in Lisbon, Portugal, at King's College, London, and at the Sorbonne in Paris. Eventually dropping out of academia, he did stints in advertising and journalism, the latter bringing him, in 1967, to Hong Kong, where he was dispatched to set up an office for The Overseas Weekly, a tabloid serving the American armed forces stationed in the region during the Vietnam war. It didn't take long, however, for the entrepreneurial bug to bite, encouraged by the city's light-touch administration of new businesses.

"You buy your registration, put it on the wall and they leave you in peace … a wonderful incentive; I would never have thought of opening my own business in Germany," he recalls.

Earnings from a string of successful enterprises over the next two decades provided the financial float to get his flagship music business up and running in 1987. Its name was selected from a stack of shell companies named after Greek islands. ("Rhodes, no; Crete, no; Lesbos, obviously no; Naxos - oh, [Richard Strauss' opera] Ariadne auf Naxos; it's easily pronounced in every language and has classical connotations.")

Twenty-five years on, the neatest way to describe the reputation Naxos has achieved would be with the adjectives "encyclopaedic" and "affordable". The comprehensiveness for which the company is famed is illustrated by the fact that the digital Naxos music library gives subscribers access to more than a million tracks online, with the number growing daily. Affordability, however, was there from the start.

CDs started to replace vinyl LPs in the mid-1980s, giving better-heeled music lovers a new aural experience. Heymann's eye, however, was focused on those with less deep pockets.

"When CDs entered the market place," he says, "they sold at an international price level of about HK$150, so nobody bought them. When I came up with my cheap CDs at the same price as an LP - HK$39.50 at the time - it was a sensation." His discs also competed in terms of playing time: never below 55 minutes, compared with 35 to 40 minutes from the major companies in Europe and the US, including Polygram, Decca, EMI and Deutsche Grammophon. It was also notable, though often overlooked by snooty connoisseurs, that his were all new recordings, not handy re-issues from a back catalogue.

Heymann thus secured his first competitive advantage in the record industry, by marrying budget-conscious buyers with brand-new goods. The industry Goliaths were under attack from a tiny upstart; how would the giants fight back?

"I must say they never played dirty," Heymann says. "I was always looking over my shoulder, worried that the majors would come after me. But we did 100 [discs] of popular repertoire, and they left me in peace."

Expansion from core popular repertoire to baroque works, early music and American composers was gradually rolled out - without inflating the price tag. Because of the misconception that cheap meant inferior, Naxos was given its own poor man's corner in record stores ("the most wonderful marketing advantage imaginable"), but the penny gradually dropped with shoppers. British actor Simon Callow was among them. He gave the toast to Heymann earlier this year at the London celebrations for the company's 25th anniversary, one of 19 such events held worldwide.

"I took a patronising and cursory glance at a Naxos stack in a record shop," Callow recalled, "and there spread out in front of me was a simply extraordinary repertory of works in every genre, from across the ages, and from every nation on the face of the Earth, newly recorded, by instantly recognisable artists, many of them among the most exciting new performers of their time. There were whole cycles of symphonies, quartets, sonatas; there were operas; there were entire ballets. I walked away from that shop weighed down with more than a dozen CDs."

It had taken a number of twists and turns, however, to get a spread like that on the table.

In 1969, Heymann quit his job at The Overseas Weekly and transformed himself into a mail-order conduit for the US military, supplying cameras, watches and hi-fi equipment. When the war ended, in 1975, his experience with the latter and his connections with world-class providers such as Bose (audio equipment) and Revox (tape recorders) offered a bridge to his next venture: establishing a studio business in China, where he built the country's first modern recording facilities, including those of China Central Television.

"When China opened up, they had karaoke bars and every one of them had Bose speakers," Heymann says. "Those were two really profitable businesses and that money I ploughed into the record business," which eventually became a two-headed cash cow, milking both the potential of its own digital recording resources and the physical distribution of CDs.

Marco Polo was Heymann's first full-price label. Established in 1982, it sold recordings of Chinese music played by the Singapore Symphony Orchestra and the Hong Kong Philharmonic. The players wanted to branch out into Western repertoire; Heymann saw no buyers for recordings of standard works by those ensembles, "but if we record completely unknown works, world premiere recordings," he prophesied, "they will buy them regardless of who plays."

Eastern Europe was the next, somewhat unexpected piece in Heymann's jigsaw. He was already acting as a distributor in Hong Kong for Hungarian, Czech and Slovak labels, which suggested he move his recording base to somewhere like Bratislava or Budapest. "So when Naxos started, in 1987, we already had recording machinery set up in Eastern Europe and that's why the first [few hundred] recordings were made there."

Quite why the major recording companies were so uninterested in this presumptuous new kid on the block is mystifying. What was the reason for allowing him to dig in his roots like this?

"Because I was in Hong Kong," Heymann says. "They referred to me as that crazy German with his budget label; he will never succeed. I was under their radar and they didn't know what was going to hit them."

In 1990, he made the decision to produce the complete works of the great composers: Beethoven first, then Mozart; and by the mid-90s, the oeuvres of many big names were captured - "every note they wrote".

Expansion into opera started in 1992, with recordings of all the works by Mozart and Puccini, plus the most important ones from the Verdi catalogue; and exploration of the genre continues today, with a complete Rossini opera project in the pipeline.

Capturing performances on CD was one thing; distributing them was another. Getting discs onto shelves proved problematic because nobody wanted to talk to a budget label. Heymann's answer was to start his own web of distribution companies in the biggest markets, starting with Britain, in 1994.

The most attractive opportunities, however, lay - tantalisingly - in the US, where Heymann found his path littered with potholes. He first tried licensing his wares to a heavy metal label he was, in turn, representing in Hong Kong, hoping to establish a kind of business synergy to balance the ups and downs of two such unlikely bedfellows. When that didn't work, he tried setting up his own distribution company based in New Jersey, which proved fruitless: "The person who was recommended turned out to be not very straightforward, to put it mildly, and he didn't really know much about classical music. But it was a start."

Moving the office from New Jersey to Nashville in June 1998 was the game-changer. "It was one of the few really good decisions I made in my life," Heymann says. The town was home to thriving scenes of Christian rock music, country and western and bluegrass, and had a strong publishing base - everything except a classical arm. "They welcomed us as a missing link in the Nashville music machinery."

With Naxos now established on American soil, it was getting a bit late in the day for the major companies to pose any serious opposition to its seemingly inexorable rise.

Expansion of the Naxos catalogue continued apace while new recordings were made to appeal to individual national tastes, with differentiated products for different countries. By the turn of the century, Naxos was able to proclaim itself the world's leading classical record label in terms of number of new releases and the breadth and depth of its catalogue; Grammy nominations and awards would be a later yardstick. More to do with quantity than quality, surely that claim to world dominance was dismissed as hyperbole by his competitors?

"No," says Heymann. "That's the amazing thing."

Cyberspace was the final frontier. Heymann found himself staring into it not so much by dint of personal technical wizardry or prophetic inspiration as by consequence of his voracious reading habits. In 1995, he had read in an American journal that the internet would be the future of music distribution and he put his faith and his money behind that opinion.

"In 1996, we made the whole of the Naxos and Marco Polo catalogues available for streaming online. The idea was that people would listen to part of a recording and then go to a shop to buy the CD; it was a marketing strategy. It cost me an awful lot of money because, in those days, bandwidth and servers were very expensive," Heymann says. "Fortunately, I had enough money from the studio business, so I could afford it."

When costs began to fall, he started to convert his investment in technology into what became the online Naxos Music Library in 2002. Thousands of professional orchestras and educational institutions around the globe (including, for example, every school in Ontario, Canada) make up the bulk of its subscribers, with their combined numbers giving the service a reach of some 20 million people. They enjoy access to an unparalleled resource that comprises 78,500 discs holding 1.1 million tracks of classical music, pop, rock, jazz, gospel and world music, plus "study areas" that tie in to educational curriculums in various regions of the world.

In the foothills of this mountainous cache of information sprouted sites streaming spoken-word classics (2002), broadcasts from the Naxos Web Radio (2004) and videos of ballet, opera and live concerts (2011). Classics Online launched its downloading service in 2007. E-books, iBooks and integrated media products are among the latest offerings.

Hundreds of labels other than those spawned by Naxos now contribute to this treasure trove. Some have been acquired over the years by Heymann; others simply decided to buy into the company's digital and physical distribution services, which are known for their efficiency and competence. Rumours are currently circulating that Naxos might buy EMI Classics and Virgin Classics. Bagging catalogues such as those would be a plump cherry on the cake. "Watch this space" is Heymann's only comment.

There have been spats along the way. The one that attracted most attention was in 2007, when Heymann sued Norman Lebrecht, the firebrand British music critic who published false statements about Heymann and the company in his book Maestros, Masterpieces & Madness: The Secret Life and Shameful Death of the Classical Record Industry. An undisclosed sum to cover legal costs and damages, the pulling of all unsold copies of the book and a public apology was the price Lebrecht and his publisher, Penguin Books, had to pay.

The organising committee for the 2008 Beijing Olympics also got snagged over allegations that the medal ceremonies featured a Chinese orchestra playing poached arrangements of national anthems by Slovak composer Peter Breiner, the international rights to which are owned by Naxos. Following a settlement, people were left speculating on the size of the financial balm that had been applied to dissipate the scandal.

Heymann has one recurring niggle: that Hong Kong is such a poor supporter of all his global efforts in the arts. By way of illustration, the National Library of Singapore (population 5.2 million) bought 2,000 subscriptions to the Naxos Music Library for its citizens; Hong Kong (population 7.1 million) bought 20. The lack of double taxation treaties between Hong Kong and many of Naxos' outposts is another irritation for Heymann's balance sheet, but his personal frustration goes deeper.

"In many ways, there is no support here from the government," he says, "[even though] it's the only [place] where the government controls the performing arts 100 per cent, through control of the venues and subsidies to their own cultural circles."

On the subject of his lack of involvement with the West Kowloon Cultural District development project, he adds: "I never get invited to any of this. I think the people here really don't want to know. The Hong Kong government always consults with people they know, but they don't consult with people who know."

The question marks hovering over Naxos today concern the successor to Heymann's chairmanship and the label's plans for product development. Heymann has a son, Rick, who turns 36 in December, but the reins will not be passing to him. "He has no interest in classical music at all," Heymann explains. "Maybe it's because of having a famous mum and successful dad in classical music, a sort of reaction against that. He's into indie rock. He works in the company, but he works on the fringes, handling the licensing."

Naxos is owned solely by Heymann and his wife. She continues to advise in the evaluation of new artists, spotting which of them are the real premier league performers. When Heymann turned 76 last month, however, a succession plan moved up the agenda.

"We now have a senior management of four executives and they decide the day-to-day running of the business," he says, giving a cursory wink to retirement. But, he adds, "I'm watching the first meetings, I get the minutes of the executive board meetings, and so on. I still deal with the major artists; I make all the repertoire decisions and I'm the pusher and puller still. I'm sitting, reading, joining the dots."

The dots he refers to include plans for an interactive encyclopaedia of classical music; selling music to hotels and restaurants on pre-programmed channels; and tailoring the Naxos Music Library to individual consumers by removing all the site's scholarly bells and whistles. "The consumer needs a good jukebox," Heymann says. "We're working on that consumer version."

The project that seems to have particularly caught his imagination, however, was inspired by the achievements of the Khan Academy, founded in 2006 in the US by Sal Khan, an American-Bangladeshi. He produced bite-sized, easy to understand maths lessons over the internet for a relative; she shared them with friends; their grades improved; and the whole idea blossomed into thousands of similar tutorials being made available on YouTube. "So now I'm talking to several people to organise a [similar project] for classical music, where people are taught everything from reading music, to arranging music, composition and music history," Heymann says. "That's my ultimate project."

Positioned between the company and the consumer stand the musicians chosen by Heymann to make recordings. His policy of engagement has never budged: artists are paid a flat fee with no adjustments for age, experience or cachet. A killer of a condition at first glance, it hasn't stopped musicians from returning time and again to be "in the family", as Heymann terms it. One such artist is American conductor Marin Alsop, music director of the Baltimore Symphony Orchestra and principal conductor of the Sao Paulo State Symphony Orchestra. She has more than 40 recordings on the Naxos label to her credit, but had misgivings at the outset of their relationship.

"It was strongly suggested that I should not associate myself with a 'budget' label because it would be a destructive career move," she says. "But, after looking at Klaus' mission and his business model, I was impressed and felt that his radical rethinking of the industry was both sound and resonated deeply with my own approach."

From her vantage point on the podium, Alsop recognises how the Naxos Music Library has revolutionised people's access to a wide range of repertoire, particularly new and lesser known works. "I believe this has impacted programming dramatically," she says.

Asked if she considers Heymann to be one of the most influential people in classical music today, Alsop steps out of the box in reply:

"I think speaking about Klaus' influence on classical music is too narrow. His vision as an innovative entrepreneur has resulted in the rebirth of a struggling industry. That is not only good for classical music, but for society at large.

"My hope is that we all look at our own organisations with the insight and foresight that Klaus has brought to the recording industry; to adapt and evolve and reinvent ourselves in the same way Klaus has done at Naxos. The lessons to be learned are far greater than just what takes place in the concert hall."