Planned for a July 1 start, the arrangement will include code sharing. That will allow Hawaiian to offer seats to smaller airports, using Hawaiian's ticketing code in travel industry computers but carrying the passengers on Mahalo's aircraft.
The main change at the beginning will be to allow Hawaiian to offer more flights to Molokai.
Hawaiian and Mahalo also are seeking ways to cooperate for other destinations, including the Kapalua-West Maui Airport which neither currently serves.
Hawaiian has one daily flight to Molokai, a 139-seat DC-9 jet service. It now will be able to sell tickets on five additional flights, using Mahalo's existing daily flights aboard 46-seat ATR-42 turboprop aircraft.
Hawaiian said the arrangement will allow it to offer additional flights without incurring expansion costs.
"This is a partnership that makes sense for everyone concerned," said Bruce R. Nobles,
Hawaiian's president and chief executive officer. "Mahalo's Molokai flight schedule is complementary to Hawaiian's and the combination will offer our customers flight options throughout the day."
Doug Caldwell, Mahalo's vice president for marketing and sales, said the alliance will enable both airlines to increase their revenues and maintain low costs while offering improved value to their customers.
Caldwell said the arrangement should help Mahalo keep its interisland fares affordable.
Hawaiian and Mahalo said they have signed a memorandum of agreement to share services, including Hawaiian possibly providing some airport services to Mahalo.
Both carriers said they anticipate signing a definitive agreement
They also are discussing the possibility of Mahalo joining Hawaiian's frequent flyer program, Gold Plus.
Code sharing became an issue in crucial union talks that led to approvals early this year allowing Hawaiian Airlines to bring in new investors.
Hawaiian's pilots balked at signing a new contract until language was included guaranteeing they would be consulted and would not be disadvantaged by any such code sharing deal.
Aloha Airlines, serves Molokai, West Maui and other smaller airports through a sister company, IslandAir, which flies 18-seat Dash-6 turboprops.
IslandAir has 10 flights a day to Molokai (nine on Sundays) and 11 flights a day to Kapalua.