RESTRICTED STOCK AGREEMENT

Exhibit 10.5

RESTRICTED STOCK AGREEMENT

This Restricted Stock Agreement (this “Agreement”), dated as of April 25, 2006, is entered into by and among Ambassadors International, Inc. (the “Company”) and Delta Queen Steamboat Company, Inc., a Delaware corporation (“DQSC”), American Queen Steamboat, LLC, a Delaware limited liability company (“AQS”), Delta Queen Steamboat, LLC, a Delaware limited liability company (“DQS”), and Mississippi Queen Steamboat, LLC, a Delaware limited liability company (“MQS” and, collectively with DQSC, AQS, and DQS, the “Sellers,” and each individually, a “Seller”).

RECITALS

WHEREAS, the Company is the owner of 100% of the equity interests of Ambassadors Cruise Group, LLC, a Delaware limited liability company (“ACG”);

WHEREAS, the Sellers and ACG are parties to that certain Asset Purchase Agreement, dated as of April 6, 2006 (the “Purchase Agreement”); and

WHEREAS, as partial consideration for the purchase by ACG of the Acquired Assets (as defined in the Purchase Agreement), the Company has agreed to issue to DQSC an aggregate of 100,000 unregistered shares of the Company’s common stock, par value $0.01 per share (the “Restricted Shares”), upon the satisfaction of certain conditions provided for in this Agreement.

ARTICLE I

ISSUANCE OF RESTRICTED SHARES

1.1 Issuance of Restricted Stock. The Company hereby agrees to issue to DQSC the Restricted Shares, upon the terms and conditions set forth in this Agreement, if the Net Revenue generated by DQSC for any one of calendar years 2007, 2008 or 2009 exceeds $115,000,000. Such issuance shall occur within thirty (30) days after the Company’s first receipt of audited financial statements demonstrating satisfaction of such condition. For avoidance of doubt, if the foregoing condition is not satisfied following the Company’s receipt of audited financial statements for the calendar year 2009, then DQSC shall not be entitled to receive any Restricted Shares and this Agreement shall automatically terminate.

“Net Revenue” means Gross Revenue, less all discounts reasonably determined and applied by ACG, including, but not limited to early booking discounts and group discounts, credit card fees, commissions and other allowances. The Company agrees not to, and agrees to cause ACG not to, undertake any action with the intent of reducing or avoiding Net Revenue solely for the purpose of avoiding the satisfaction of the foregoing conditions.

“Gross Revenue” means all revenue including but not limited to fare revenue, onboard revenue, passenger air revenue, cancellations, insurance and land based revenue.

1.2 Conditions to Issuance of Stock Certificates. The Restricted Shares, or any portion thereof, may be either previously authorized but unissued shares or issued shares which have been reacquired by the Company. Such Restricted Shares shall be fully paid and nonassessable. The Company shall not be required to issue or deliver any Restricted Shares prior

1

to the obtaining of any approval or other clearance from any state or federal governmental agency which the Company shall, in its absolute discretion, determine to be necessary or advisable.

1.3 Rights as Stockholder. Except as otherwise provided herein, until the issuance of the Restricted Shares, DQSC shall not have any of the rights of a stockholder with respect to said Restricted Shares.

1.4 Shares Freely Tradable. On or prior to the ninetieth day after the issuance of the Restricted Shares, the Company shall prepare and file with the Securities and Exchange Commission (the “SEC”) a registration statement on Form S-3 (a “Registration Statement”) registering the resale of the Restricted Stock, provided that the Company is eligible to use a Registration Statement on Form S-3 at such time. The Company shall use its reasonable best efforts to meet the qualifications for use on Form S-3 and to have the Registration Statement declared effective under the Securities Act of 1933, as amended (the “Securities Act”) as promptly as practicable after such filing. The Company shall also take any reasonable action (other than qualifying to do business in any jurisdiction in which it is not now so qualified or to file a general consent to service of process) required to be taken under any applicable state securities laws in connection with the resale of the Restricted Shares, and DQSC shall furnish all information concerning DQSC as may be reasonably requested in connection with any such action. The Company will advise DQSC, promptly after it receives notice thereof, of the time when the Registration Statement has been declared effective by the SEC or any supplement or amendment has been filed, the issuance of any stop order, the suspension of the qualification of the Restricted Shares registered thereon, or any request by the SEC for amendment of the Registration Statement or comments thereon and responses thereto or requests by the SEC for additional information. The Company shall furnish DQSC with a copy of the prospectus contained in the Registration Statement, as declared effective by the SEC. All registration expenses incurred by the Company in connection with the registration of the Restricted Shares shall be borne by the Company. Subject to customary black-out periods applicable to DQSC, for which the Company shall provide notice of black-out periods applicable to DQSC and during which time DQSC shall not sell Restricted Shares registered pursuant to the Registration Statement, the Company agrees to use commercially reasonable efforts to keep current and effective the Registration Statement until such time as it may be withdrawn pursuant to the last sentence of this Section 1.4. Upon the expiration of a black-out period, the Company shall provide notice to DQSC, at which time DQSC may dispose of Restricted Shares. Notwithstanding the forgoing, the Company shall not be obligated to file a Registration Statement if, and shall be entitled to withdraw a Registration Statement when, the Restricted Shares have been sold by DQSC or may be sold by DQSC under Rule 144(k) under the Securities Act.

ARTICLE II

REPRESENTATIONS AND WARRANTIES OF THE HOLDERS

Each Seller represents and warrants to the Company and ACG that the statements contained in this Article II are correct and complete as of the date of this Agreement.

2

2.1 Organization. DQSC is a corporation duly organized, validly existing, and in good standing under the laws of the State of Delaware. AQS, DQS and MQS are duly organized, validly existing, and in good standing under the laws of the State of Delaware.

2.2 Authorization of Transaction. The Sellers have full power and authority to execute and deliver this Agreement and to perform their obligations hereunder. The execution of this Agreement by the Sellers and the delivery and performance by such parties of this Agreement has been duly authorized. Any and all acts and other proceedings required for the due and valid authorization, execution, delivery and performance by the Sellers of this Agreement have been validly and appropriately taken. This Agreement constitutes the valid and legally binding obligation of the Sellers, enforceable in accordance with its terms and conditions. The Sellers need not give any notice to, make any filing with, or obtain any authorization, consent, or approval of any government or governmental authority in order to consummate the transactions contemplated by this Agreement.

2.3 Noncontravention. Neither the execution and the delivery of this Agreement, the consummation of the transactions contemplated hereby, nor the performance by the Sellers of their obligations under this Agreement, will violate any constitution, statute, regulation, rule, injunction, judgment, order, decree, ruling, charge or other restriction of any government, governmental authority or court to which any Seller is subject.

2.4 Investor Representations.

(a) The Sellers confirm that they have been given sufficient access to information regarding the Company and in connection with DQSC’s receipt of the Restricted Shares under this Agreement, including the opportunity to ask questions of, and receive answers from, persons acting on behalf of the Company and concerning the Company’s financial affairs, prospects and condition.

(b) The Sellers represent and warrant that (i) they are resident in or otherwise subject to the securities legislation of the United States, and the issuance of the Restricted Shares to DQSC under this Agreement shall occur only in the United States; (ii) the Sellers, by reason of their business or financial expertise, have the capacity to protect their own interests in connection with the acquisition of the Restricted Shares; and (iii) each Seller is an “accredited investor” as defined in Rule 501 of Regulation D of the Securities Act.

(c) The Sellers represent, warrant and covenant that they shall acquire the Restricted Shares issuable under this Agreement for their own account and not for the account or on behalf of others, and they are doing so with the intent of retaining such Restricted Shares as an investment and without the current intent to redistribute the Restricted Shares.

(d) The Sellers acknowledge that: (i) no securities commission or similar authority has reviewed or passed on the merits of the Restricted Shares issuable under this Agreement; (ii) there is no government or other insurance covering such Restricted Shares; and (iii) there are risks associated with the acquisition of the Restricted Shares, including without limitation those described in the Company’s filings with the Securities and Exchange Commission.

3

(e) The Sellers acknowledge that (i) they must and shall bear the economic risk of holding the Restricted Shares issuable under this Agreement, which may be for an indefinite period of time, because at the time such Restricted Shares are issued they will not have been registered under the Securities Act or any other securities law and, therefore, cannot be sold unless they are subsequently registered under applicable federal and state securities laws or an exemption from such registration is available; (ii) the Restricted Shares may not be resold or transferred on the official stock transfer records of the Company without furnishing to the Company an opinion of counsel reasonably acceptable to the Company that such sale or transfer of the Restricted Shares will not violate the registration provisions of applicable federal and state securities laws; and (iii) certificates representing the Restricted Shares shall have endorsed on them a restrictive legend to this effect.

(f) The Sellers acknowledge that the Company is relying on the representations, warranties, covenants and acknowledgments in this Section 2.4 to ensure that any Restricted Shares issued under the terms of this Agreement can be issued in reliance on exemptions from registration requirements under United States federal and state securities laws.

ARTICLE III

REPRESENTATIONS AND WARRANTIES OF THE COMPANY

The Company represents and warrants to DQSC that the statements contained in this Article III are correct and complete as of the date of this Agreement.

3.1 Organization. The Company is a corporation duly organized, validly existing, and in good standing under the laws of the State of Delaware. The Company is qualified to do business as a foreign corporation and is in good standing in each jurisdiction where the character of its properties owned or leased or the nature of its activities make such qualification necessary.

3.2 Authorization of Transaction. The Company has full power and authority to execute and deliver this Agreement and to perform its obligations hereunder. The execution of this Agreement by the Company and the delivery and performance by the Company of this Agreement has been duly authorized. Any and all acts and other proceedings required for the due and valid authorization, execution, delivery and performance by the Company of this Agreement have been validly and appropriately taken. This Agreement constitutes the valid and legally binding obligation of the Company, enforceable in accordance with its terms and conditions. The Company need not give any notice to, make any filing with, or obtain any authorization, consent, or approval of any government or governmental authority in order to consummate the transactions contemplated by this Agreement.

3.3 Noncontravention. Neither the execution and the delivery of this Agreement, the consummation of the transactions contemplated hereby, nor the performance by the Company of its obligations under this Agreement, will violate any constitution, statute, regulation, rule, injunction, judgment, order, decree, ruling, charge, or other restriction of any government, governmental authority, or court to which the Company is subject.

4

3.4 Valid Issuance. The Restricted Shares will be, upon issuance, duly authorized, validly issued, fully paid, nonassessable, and free of and not issued in violation of preemptive rights.

3.5 Authorized and Issued Shares. The Company has                          total authorized common shares of which                      common shares are issued and outstanding on the date hereof.

ARTICLE IV

OTHER PROVISIONS

4.1 Adjustment for Stock Split; Change of Control. In the event of any stock dividend, stock split, reverse stock split, recapitalization, combination, reclassification, or similar change in the capital structure of the Company occurring after the date of this Agreement the Company shall make adjustments to the Restricted Shares and the number of Restricted Shares such that the percentage of total outstanding shares of the Company that are Restricted Shares subject to this Agreement after any or all such events shall be the same as the percentage of total outstanding shares of the Company that are Restricted Shares subject to this Agreement prior to any or all such events. The provisions of this Agreement shall be similarly adjusted for any merger or consolidation of the Company with or into another corporation in which the Company is not the surviving corporation.

4.2 Listing. On or prior to the issuance of the Restricted Shares, the Company shall use its commercially reasonable best efforts to cause the Restricted Shares to be listed on the Nasdaq National Market and to obtain all governmental approvals necessary for such listing.

4.3 Notices. Any notice to be given under the terms of this Agreement to the Company shall be addressed to the Company in care of the Secretary of the Company, and any notice to be given to DQSC shall be addressed to DQSC at the address given beneath its signature on the signature page hereof. By a notice given pursuant to this Section 4.3, any party hereto may hereafter designate a different address for notices to be given to that party. Any notice shall be deemed duly given when sent via email or when sent by certified mail (return receipt requested) and deposited (with postage prepaid) in a post office or branch post office regularly maintained by the United States Postal Service.

4.4 Titles. Titles are provided herein for convenience only and are not to serve as a basis for interpretation or construction of this Agreement.

4.5 Governing Law; Severability. This Agreement shall be administered, interpreted and enforced under the laws of the State of Delaware without regard to conflicts of laws thereof. Should any provision of this Agreement be determined by a court of law to be illegal or unenforceable, the other provisions shall nevertheless remain effective and shall remain enforceable.

4.6 Conformity to Securities Laws. DQSC acknowledges that the Purchase Agreement and this Agreement are intended to conform to the extent necessary with all provisions of the Securities Act and the Securities Exchange Act of 1934, as amended, and any and all regulations and rules promulgated by the Securities and Exchange Commission

5

thereunder, and state securities laws and regulations. Notwithstanding anything herein to the contrary, the Purchase Agreement and this Agreement shall be administered, and the Restricted Shares are to be issued, only in such a manner as to conform to such laws, rules and regulations. To the extent permitted by applicable law, the Purchase Agreement and this Agreement shall be deemed amended to the extent necessary to conform to such laws, rules and regulations.

4.7 Amendments. This Agreement may not be modified, amended or terminated except by an instrument in writing, signed by DQSC and by a duly authorized representative of the Company.

4.8 Successors and Assigns. The Company may assign any of its rights under this Agreement to single or multiple assignees, and this Agreement shall inure to the benefit of the successors and assigns of the Company. Subject to the restrictions on transfer herein set forth, this Agreement shall be binding upon DQSC and its successors and assigns.

[SIGNATURE PAGE TO FOLLOW]

6

IN WITNESS WHEREOF, the parties have caused their duly authorized representatives to execute this Agreement as of the date first above written.

7

8