Exhibit 10.37

MUTUAL RELEASE AND SEVERANCE AGREEMENT

This Mutual Release and Severance Agreement (hereafter “Agreement”) dated as of February 22, 2008, is hereby entered into between Michael S. Ruley (“Executive”), and Hawaiian Telcom Holdco, Inc., a Delaware corporation (the “Employer”).

WHEREAS, Employer and Executive entered into an Employment Agreement dated October 1, 2004 (the “Employment Agreement”);

WHEREAS, Employer and Executive entered into a Non-Qualified Stock Option Agreement dated November 8, 2005 (the “Stock Option Agreement”) pursuant to the terms of the Stock Option Plan of Hawaiian Telcom Holdco, Inc. (the “Stock Option Plan”);

WHEREAS, Employer, Executive and certain other parties thereto entered into an Amended and Restated Limited Partnership Agreement dated May 13, 2005 (the “LP Agreement”); and

WHEREAS, Executive and Employer have agreed that Executive shall terminate his employment from the Employer under the terms hereof.

NOW THEREFORE, in exchange for the good and valuable consideration set forth herein, the adequacy of which is specifically acknowledged, Executive and Employer (the “parties”) hereby agree as follows:

1.                                       Termination of Employment. Executive acknowledges that his employment with Employer shall terminate effective as of February 4, 2008 (the “Termination Date”). Executive’s termination will be classified by Employer as a voluntary resignation.

2.                                       Severance Payments.

(a)                                  No later than fifteen days after Executive tenders to the Employer a signed Mutual Release in the form of Exhibit A, provided that such tender occurs no earlier than the Termination Date and no later than February 28, 2008 and that such Mutual Release has not been revoked by Executive, the Employer will pay Executive the following amounts, less applicable withholdings:

(1)                                  $1,117,272;

(2)                                  Any bonus which has been declared or earned but not yet paid for fiscal year 2007;

(3)                                  $71,340 (with respect to Executive’s annual COLA payment for 2007);

(4)                                  Any business expenses incurred by the Executive in accordance with the Employer’s policies not yet paid to the Executive;

(5)                                  The value of all accrued, unused vacation days based on Executive’s service to the Employer which the parties agree is 320.33 hours;

(6)                                  Any other amounts due to the Executive arising from the Executive’s participation in, or benefits under, any employee benefit plans, programs or arrangements; plus

(7)                                  $20,000 (with respect to accrued but unused airfare between Honolulu and the United States mainland) (the “Airfare Payment”).

(b)                                 No earlier than thirty days after Executive tenders to the Employer a signed Mutual Release in the form of Exhibit A, provided that such tender occurs no earlier than the Termination Date and no later than February 28, 2008 and that such Mutual Release has not been revoked by Executive, the Employer will pay Executive within 30 days of Executive submitting expenses to Employer for payment the following amounts, less applicable withholdings:

(1)                                  Pursuant to Section 3(f) of the Employment Agreement and as outlined in the Company’s Executive Relocation Benefits Plan, reimbursement for all relocation expenses (“Relocation Reimbursement”) incurred by the Executive due to his relocation back to the mainland United States at a location of his choice, including payment  of up to a 6% real estate broker commission fee (“Hawaiian Broker Fee”) paid by the Executive on the sale of his Hawaiian residence, plus an additional payment in an amount such that, after payment by the Executive of all the income taxes imposed on the Relocation Reimbursement and the additional payment, the Executive would retain an amount equal to Relocation Reimbursement; and

(2)                                  Reimbursement for any lease termination penalties (“Lease Reimbursement”) incurred by Executive pursuant to Section 3(i) of the Employment Agreement (but subject to the limitations contained therein) plus an additional payment in an amount such that, after payment by the Executive of all the income taxes imposed on the Lease Reimbursement and the additional payment, the Executive would retain an amount equal to Lease Reimbursement.

3.                                       Continued Medical Benefits. Following the Termination Date, Employer shall continue coverage (at the Company’s expense) for Executive and his dependents under all Company group health benefit plans in which Executive and any dependents were entitled to participate immediately prior to the Termination Date (under the same terms as during employment), including HMSA medical plan, HDS dental plan, HMSA vision plan, and Exec U Care supplemental plan, for twelve months from the Termination Date, which period shall be co-extensive with the period of coverage with respect to Executive under COBRA. . Thereafter, Executive shall be eligible for such continued coverage at his own expense for the remainder of the applicable COBRA coverage period. Except as provided in Sections 1, 2, 3, 5 and 7 hereof or by applicable law or plan documents, all other compensation, benefits or perquisites shall cease upon the Termination Date.

2

4.                                       Continued Effect of Employment Agreement. The terms and conditions of Sections 6 through 10 of the Employment Agreement shall remain in full force and effect for the applicable periods of time indicated.

5.                                       Equity in Employer. Executive shall be entitled to exercise all of his vested stock options through the thirtieth day following the Termination Date in accordance with the terms of the Stock Option Agreement and Stock Option Plan.

6.                                       Residual Duties. The parties agree and intend that any and all duties of loyalty, fidelity, and confidentiality running from Executive to Employer and arising out of the common law as a consequence of the parties’ employment relationship shall continue in full force and effect between the parties until the Termination Date; provided, however, that neither this paragraph nor any other portion of this Agreement shall be interpreted to diminish any residual duties or obligations of Executive to Employer that may arise or continue in effect under the common law after the Termination Date.

7.                                       Attorneys’ Fees. Executive shall be reimbursed for reasonable attorneys’ fees and costs incurred in connection with the negotiation and execution of this Agreement in an amount not to exceed $4,500.

8.                                       No Other Payments. Executive understands and agrees that Employer shall make no other payments to Executive, and shall have no other obligations to Executive except as described in this Agreement or as otherwise required by law or plan documents.

9.                                       Taxes. To the extent any taxes may be due on the payments to Executive provided in this Agreement beyond any withheld by Employer, Executive agrees to pay them himself and to indemnify and hold Employer and other entities released by Executive pursuant to the terms hereof (including Exhibit A)  harmless for any tax claims or penalties resulting from such payments. Executive further agrees to provide any and all information pertaining to Executive upon request as reasonably necessary for Employer and other entities so released to comply with applicable tax laws.

10.                                 Severability. Except as otherwise specified below, should any portion of this Agreement be found void or unenforceable for any reason by a court of competent jurisdiction, the court should attempt to limit or otherwise modify such provision so as to make it enforceable, and if such portion cannot be modified to be enforceable, the unenforceable portion shall be deemed severed from the remaining portions of this Agreement, which shall otherwise remain in full force and effect. If any portion of this Agreement is so found to be void or unenforceable for any reason in regard to any one or more persons, entities, or subject matters, such portion shall remain in full force and effect with respect to all other persons, entities, and subject matters. In the event Executive should in the future contend that Executive’s release of claims pursuant to Exhibit A is for any reason void, imperfect, or incomplete, Executive may not pursue any claim against Employer (or any other party intended to be released thereby) to establish the invalidity of the release or premised (in whole or in part) on the invalidity of the release before or without repaying to Employer the full amount of such cash payments he has received, less the reasonable value of services actually provided pursuant to this Agreement, and applicable statutes of limitations shall be deemed to run in regard to Executive’s claims without regard to the parties’ entry into this Agreement. The preceding sentence shall not operate to limit the scope or effect of Executive’s covenant not to sue.

3

11.                                 Understanding and Authority. The parties understand and agree that all terms of this Agreement are contractual and are not a mere recital, and represent and warrant that they are competent to covenant and agree as herein provided.

12.                                 Internal Revenue Code Section 409A. Certain payments and benefits payable under this Agreement are intended to comply with the requirements of Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”). Certain payments and benefits payable under this Agreement are intended to be exempt from the requirements of Section 409A of the Code. This Agreement shall be interpreted in accordance with the applicable requirements of, and exemptions from, Section 409A of the Code and the Treasury Regulations thereunder. To the extent the payments and benefits under this Agreement are subject to Section 409A of the Code, this Agreement shall be interpreted, construed and administered in a manner that satisfies the requirements of Sections 409A(a)(2), (3) and (4) of the Code and the Treasury Regulations thereunder (subject to the transitional relief under Internal Revenue Service Notice 2005-1, the Proposed Regulations under Section 409A of the Code, Internal Revenue Service Notice 2006-79, Internal Revenue Service Notice 2007-78 and other applicable authority issued by the Internal Revenue Service). As provided in Internal Revenue Notice 2007-78, notwithstanding any other provision of this Agreement, with respect to an election or amendment to change a time or form of payment under this Agreement made on or after January 1, 2008 and on or before December 31, 2008, the election or amendment shall apply only with respect to payments that would not otherwise be payable in 2008 and shall not cause payments to be paid in 2008 that would not otherwise be payable in 2008. If the Employer and the Executive determine that any compensation, benefits or other payments that are payable under this Agreement and intended to comply with Sections 409A(a)(2), (3) and (4) of the Code do not comply with Section 409A of the Code, the Treasury Regulations thereunder and other applicable authority issued by the Internal Revenue Service, the Employer and the Executive agree to amend this Agreement, or take such other actions as the Employer and the Executive deem reasonably necessary or appropriate, to comply with the requirements of Section 409A of the Code, the Treasury Regulations thereunder and other applicable authority issued by the Internal Revenue Service, while preserving the economic agreement of the parties. In the case of any compensation, benefits or other payments that are payable under this Agreement and intended to comply with Sections 409A(a)(2), (3) and (4) of the Code, if any provision of the Agreement would cause such compensation, benefits or other payments to fail to so comply, such provision shall not be effective and shall be null and void with respect to such compensation, benefits or other payments, and such provision shall otherwise remain in full force and effect. Consistent with the foregoing, the parties intend that the Termination Date shall be the date of the Executive’s “separation from the service” with the Employer within the meaning of Code Section 409A(a)(2)(A)(i).

13.                                 Mutual Release. Executive understands, agrees and represents that the covenants made herein and the Mutual Release to be executed by both parties pursuant to Exhibit A may affect rights and liabilities of substantial extent and agrees that the covenants and releases provided herein are in Executive’s best interest. Executive represents and warrants that in negotiating and executing this Agreement Executive has had an adequate opportunity to consult with competent legal counsel of his choosing concerning the meaning and effect of each term and provision hereof, and that there are no representations, promises, or agreements between Employer and Executive other than those expressly set forth in writing herein.

4

14.                                 Governing Law. This Agreement shall be governed by the laws of the State of New York, without reference to conflicts of law principles.

15.                                 Entire Agreement. This Agreement, including Exhibit A attached hereto, and the Consulting Agreement of even date, embody the entire agreement between the parties with regard to its subject matter. This Agreement supersedes any and all prior agreements and understandings between the parties with respect to its subject matter.

16.                                 Amendments. This Agreement may not be amended or changed except by a written agreement signed by both parties.

17.                                 Successors and Assigns. This Agreement shall be binding on the parties and their respective successors and assigns.

The parties have carefully read this Agreement in its entirety; fully understand and agree to its terms and provisions; and intend and agree that it is final and binding on all parties.

[signature page follows]

5

IN WITNESS WHEREOF, and intending to be legally bound, the parties have executed the foregoing on the dates shown below.

6

EXHIBIT A

MUTUAL RELEASE

This Mutual Release (hereafter “Agreement”), dated February         , 2008 is hereby entered into between Michael S. Ruley (“Executive”), and Hawaiian Telcom Holdco, Inc., a Delaware corporation (the “Employer”).

WHEREAS, Employer and Executive entered into a Mutual Release and Severance Agreement (the “Severance Agreement”) dated February 22, 2008, which Agreement contemplates the Execution of this Mutual Release.

THEREFORE, in exchange for the good and valuable consideration set forth herein, the adequacy of which is specifically acknowledged, Executive and Employer (the parties”) hereby agree as follows:

1.                                       General Release of Claims by Executive. Executive agrees for Executive, Executive’s spouse and child or children (if any), Executive’s heirs, beneficiaries, devisees, executors, administrators, attorneys, personal representatives, successors and assigns, hereby forever to release, discharge, and covenant not to sue Employer, Employer’s past, present, or future parent, affiliated, related, and/or subsidiary entities (collectively “Affiliates”), and all of their past and present directors, shareholders, officers, general or limited partners, employees, agents, and attorneys, and agents and representatives of such entities, and employee benefit plans in which Executive is or has been a participant by virtue of his employment with Employer, from any and all claims, debts, demands, accounts, judgments, rights, causes of action, equitable relief, damages, costs, charges, complaints, obligations, promises, agreements, controversies, suits, expenses, compensation, responsibility and liability of every kind and character whatsoever (including attorneys’ fees and costs), whether in law or equity, known or unknown, asserted or unasserted, suspected or unsuspected, which Executive has or may have had against such entities based on any events or circumstances arising or occurring on or prior to the Termination Date (or, with respect to claims of disparagement, arising or occurring on or prior to the date this Agreement is executed), arising directly or indirectly out of, relating to, or in any other way involving in any manner whatsoever, (a) Executive’s employment with Employer or the termination thereof or (b) the Executive’s status at any time as a holder of any securities of Employer, and any and all claims arising under federal, state, or local laws relating to employment, or securities, including without limitation claims of wrongful discharge, breach of express or implied contract, fraud, misrepresentation, defamation, or liability in tort, claims of any kind that may be brought in any court or administrative agency, any claims arising under Title VII of the Civil Rights Act of 1964, the Age Discrimination in Employment Act, the Americans with Disabilities Act, the Fair Labor Standards Act, the Employee Retirement Income Security Act, the Family and Medical Leave Act, the Securities Act of 1933, the Securities Exchange Act of 1934, and similar state or local statutes, ordinances, and regulations, provided, however, notwithstanding anything to the contrary set forth herein, that this release shall not extend to (i) benefit claims under employee pension benefit plans in which Executive is a participant by virtue of his employment with  Employer or to benefit claims under employee welfare benefit plans for occurrences (e.g., medical care, death, or onset of disability) arising

7

after the execution of this Agreement by Executive, (ii) any obligation assumed under this Agreement by any party hereto, and (iii) any claim for indemnification or insurance coverage pursuant to Section 23 of the Employment Agreement.

2.                                       General Release of Claims by the Employer. The Employer agrees, for the Employer, its Affiliates, and all of their past and present directors, shareholders, officers, general or limited partners, employees, agents, and attorneys, and agents and representatives of such entities, and employee benefit plans in which Executive is or has been a participant by virtue of his employment with Employer and all of their respective predecessors, successors and assigns, to hereby forever to release, discharge, and covenant not to sue Executive, from any and all claims, debts, demands, accounts, judgments, rights, causes of action, equitable relief, damages, costs, charges, complaints, obligations, promises, agreements, controversies, suits, expenses, compensation, responsibility and liability of every kind and character whatsoever (including attorneys’ fees and costs), whether in law or equity, known or unknown, asserted or unasserted, suspected or unsuspected, which the Employer has or may have had against Executive based on any events or circumstances arising or occurring on or prior to the Termination Date, including without limitation any and all claims arising out of Executive’s employment with the Company or the termination thereof provided, however, notwithstanding anything to the contrary set forth herein, that this release shall not extend to (a) any claim which relates to or arises from any criminal activity of Executive, and (b) any obligation assumed under this Agreement by any party hereto.

3.                                       Release of Age Discrimination Claims; Periods for Review and Reconsideration.

(a)                                  Executive understands that this Agreement includes a release of claims arising under the Age Discrimination in Employment Act (ADEA). Executive understands and warrants that he has been given a period of twenty-one (21) days to review and consider this Agreement. Executive is hereby advised to consult with an attorney prior to executing the Agreement. By his signature below, Executive warrants that he has had the opportunity to do so and to be fully and fairly advised by that legal counsel as to the terms of the Agreement. Executive further warrants that he understands that he may use as much or all of his 21-day period as he wishes before signing, and warrants that he has done so.

(b)                                 Executive further warrants that he understands that he has seven (7) days after signing this Agreement to revoke the Agreement by notice in writing to Jed W. Brickner, Latham & Watkins, 885 Third Avenue, Suite 1000, New York, N.Y. 10022. This Agreement shall be binding, effective, and enforceable upon both parties upon the expiration of this seven-day revocation period without Mr. Brickner having received such revocation, but not before such time.

[signature page follows]

8

IN WITNESS WHEREOF, and intending to be legally bound, the parties have executed the foregoing on the dates shown below.

9