Located at the eastern edge of the present-day Tseung Kwan O New Town, the district of Hang Hau was a collection of traditional villages with a market town facing Junk Bay before the 1970s. Transportation to and from Hang Hau then relied on kai-to ferries. Route 91A, the first bus route serving Hang Hau Town, was introduced on April 1, 1976, serving between Hang Hau and Chuk Yuen. After the city's Mass Transit Railway system commenced operation, the route was renamed 91M and truncated to Diamond Hill MTR Station with effect from December 16, 1979; it was further curtailed to Choi Hung MTR Station just 4 years later, on November 3, 1983. The Kowloon-side terminus of route 91M would return to Diamond Hill 14 years later, on November 2, 1997, this time to tie in with the opening of Diamond Hill Station Public Transport Interchange inside Plaza Hollywoodshopping centre. The development of Tseung Kwan O New Town has changed route 91M a lot, as Hang Hau became part of the new town in the early 1990s. 91M was no longer the only route serving Hang Hau with the advent of the Tseung Kwan O Tunnel, which brought residents numerous new routes connecting TKO with the urban area. As the population of Hang Hau district was initially expected to dwindle during the development, KMB once proposed the withdrawal of this route in 1988 and obtained permission from the Government's Transport Department. The latter responded by inviting tenders to the operation rights of a new green minibus route running almost the same route with 91M. However, plans of cancelling route 91M was ultimately shelved, and the green minibus route went into operation anyway. It was eventually extended to On Ning Garden inside the newly reclaimed and -developed part of Hang Hau in 1991. The establishment of the Hong Kong University of Science and Technology in 1991 also changed the prospect of route 91M. Peak-hour departures of the route started serving the newly founded university in March 1992, and by 1994, all 91M departures throughout the day would call at HKUST's bus station on University Road. The major group of passengers served by this route gradually shifted from Hang Hau inhabitants to HKUST faculty and students since then. Route 298M, serving between Po Lam and HKUST, was cancelled with effect from June 19, 2004 due to low patronage. Route 91M was extended from Hang Hau to Po Lam effective from the same day as a replacement.
