AMENDED AND RESTATED SHAREHOLDERSAGREEMENT

Exhibit 4.2

AMENDED AND RESTATED

SHAREHOLDERS AGREEMENT

THIS AMENDED AND RESTATED SHAREHOLDERS AGREEMENT (this “Agreement”) is made and entered into as of the 31st day of August, 2001, by and among TRX, Inc., a Georgia corporation (the “Corporation”), BCD Technology S.A., a corporation organized under the laws of Luxembourg (“BCD”) (who is a party solely for purposes of Section 2(c) hereof) and the following parties, each of which shall be a “Shareholder,” and collectively, the “Shareholders”: (i) Christopher M. Brittin, an individual resident of Virginia (“Brittin”); (ii) Susan R. Hopley, an individual resident of Virginia (“Hopley”); (iii) Gary D. Smith and Jean H. Smith, as Trustees of the Gary D. Smith and Jean H. Smith Trust (“Smith”); and (iv) F. Gilmer Siler, an individual resident of Virginia (“Siler”).

R E C I T A L S

WHEREAS, the Corporation, the Shareholders and BCD entered into a Shareholders Agreement dated November 4, 1999 (the “Original Agreement) to place certain restrictions on the transferability of the Shares (as defined below) now or hereafter owned by them, and address certain other matters with respect to the Shares and the Corporation; and

WHEREAS, the Corporation, the Shareholders and BCD desire to amend and restate the Original Agreement which, upon the effectiveness of this Agreement, shall cease to have any further force or effect;

WHEREAS, capitalized terms used but not otherwise defined herein shall have the meanings ascribed to such terms in the Contribution Agreement;

NOW, THEREFORE, in consideration of the mutual promises of the parties made in this Agreement and for other good and valuable consideration, the receipt of which is hereby acknowledged, the parties, intending to be legally bound, agree as follows:

A G R E E M E N T

1. Certain Defined Terms. As used in this Agreement, the following terms shall have the following meanings:

(a) “Affiliate” means a Person or Persons (each as defined below) who: (i) directly or indirectly, through one or more intermediaries, controls, is controlled by, or is under common control with the Person(s) in question, or (ii) is an officer, director, or shareholder of the Person(s) in question. The term “control,” as used in the immediately preceding sentence, means, with respect to a Person that is a corporation, the right to the exercise, directly or indirectly, of more than 50% of the voting rights attributable to the shares of such controlled corporation and, with respect to a Person that is not a corporation, the possession, directly or indirectly, of the power to direct or cause the direction of the management or policies of such controlled Person.

(b) “Person” means an individual, partnership, limited liability company, joint venture, association, corporation, trust or any other legal entity.

(c) “Share” or “Shares” shall mean and include shares of the Corporation’s common stock, par value $. 01 per share, and all other securities of the Corporation which may be issued in exchange for or in respect of such shares (whether by way of stock split, stock dividend, combination, reclassification or any other means);

(d) “Transfer” shall mean to transfer, sell, assign, pledge, hypothecate, give, create a security interest in or lien on, place in trust (voting or otherwise), assign or in any way encumber or dispose of directly or indirectly and whether or not by operation of law or for value.

2. Transfers by Shareholders.

(a) Transfers Generally. Except as provided in this Section 2, no Shareholder shall have the right to Transfer all or any portion of his or her Shares other than to an existing shareholder of the Corporation without the prior written consent of the Board of Directors of the Corporation.

(b) Redemption.

(1) Upon the death or permanent physical or mental disability of Brittin, Hopley, Siler or Smith (each a “Redeemable Shareholder”), or (ii) in the event that a Redeemable Shareholder employed by the Corporation, WorldTravel Technologies, L.L.C (“WTT”) or ISP, as applicable (or any successor or Affiliate entities thereof), shall no longer be employed by the Corporation, WTT or ISP (or any successor or Affiliate entities thereof) for any reason (which, for the purpose of this Section 2(b), shall be interpreted to include a party invoking any notice of termination provision in an employment agreement, regardless of the fact that actual employment with WTT or ISP (or any successor or Affiliate entities thereof) has not yet ceased), the Corporation shall have the right to redeem, or shall have the right to cause a third party to purchase, and (if the Corporation exercises such right) the Redeemable Shareholder shall sell, all of the Shares of such Redeemable Shareholder. Each of the events described in subsections (i) and (ii) above shall, for the purposes of this Agreement, be deemed a “Separation Event.” For the purpose of clause (ii) above, performing consulting services as an independent contractor and/or serving on the Board of Directors of the Corporation or WTT or ISP (or any successor or Affiliate entities thereof) shall not, singly or together, constitute employment. For the purposes of this Agreement, a permanent physical or mental disability of a Redeemable Shareholder shall be deemed to have occurred at the end of a period of one hundred and eighty (180) consecutive days during which the Redeemable Shareholder has been unable to perform the customary and usual duties for which he or she was employed. Any such redemption or purchase shall be consummated within thirty (30) days of a final determination of “fair market value” provided, however in the event of a purchase or redemption occasioned by a party invoking any notice of termination provision in an employment agreement, the date specified above shall be sixty (60) days after the date through which the employee is contractually bound to be employed by the Corporation.

2

(2) The redemption price (the “Redemption Price”) for the Shares of a Redeemable Shareholder redeemed or purchased pursuant to this Section 2(b) shall be equal to the amount which would be distributed to such Redeemable Shareholder or its representative upon the dissolution of the Corporation if the entire business of the Corporation was sold to a third party for cash at its “fair market value,” as defined and determined below.

(A) For purposes of this Section 2(b), “fair market value” shall mean the price which a sophisticated purchaser, knowledgeable in the business of the Corporation, would pay for the business of the Corporation as a going concern, taking into account goodwill and any other intangible assets of the Corporation’s business, all as determined in accordance with this Section 2(b). The “fair market value” measure to be used in connection with a purchase or redemption occasioned by a Separation Event which occurs during a given year shall be the fair market value of the Corporation as of December 31st of the year immediately preceding the year in which the Separation Event occurs If the Separation Event at issue is the invocation of a “notice of termination” provision in an employment agreement, then the “fair market value” for such purchase or redemption shall be the fair market value applicable for the year in which the notice of termination is given and not the fair market value of the actual date of the person’s termination of employment, if different. The fair market value shall be determined in good faith by the Board of Directors and shall be adopted on behalf of the Corporation and all Shareholders by operation of this Agreement unless one or more shareholders of the Corporation (the “Objecting Shareholders”), by a majority of the votes entitled to be cast in accordance with this Section 2(b)(2)(A), has objected in good faith to the previously determined fair market value through written notice to the Corporation no later than fifteen (15) days after the date of the Board of Directors’ written determination For this purpose, each shareholder of the Corporation shall be entitled to vote that number of votes equal to the percentage derived by dividing the number of Shares owned by such shareholder by the sum of the Shares owned by all other shareholders of the Corporation. In the event the Objecting Shareholders timely and properly object to the fair market value figure proposed by the Board of Directors, the Board of Directors will continue to work with the Objecting Shareholders to attempt to reach agreement on fair market value until (x) one or more shareholders of the Corporation, by a majority of the votes entitled to be cast in accordance with this Section 2(b)(2)(A), agree with the Board of Directors in writing to a fair market value, or (y) such time as either the Board of Directors or one or more shareholders of the Corporation, by a majority of the votes entitled to be cast in accordance with this Section 2(b)(2)(A), makes written demand on the other for an appraisal (an “Appraisal Demand”). In the event of an Appraisal Demand, fair market value shall be determined as set forth in Section 2(b)(2)(B)-(C).

(B) In the event of an Appraisal Demand, the Board of Directors and the Objecting Shareholders, by a majority of the votes entitled to be cast in accordance with Section 2(b)(2)(A), shall each appoint an appraiser to determine the fair market value of the business of the Corporation. Such appointments shall be made within sixty (60) days from the date of the Appraisal Demand, and shall be accomplished by each of the Board of Directors and the Objecting Shareholders by providing written notice to the other. In the event that either the Board of Directors or the Objecting Shareholders do not appoint an appraiser within such time, then such appraiser shall be appointed by the appraiser who has been appointed by either the Board of Directors or the Objecting Shareholders. Each appraiser selected hereunder shall be qualified and experienced in valuing businesses which are in the same or

3

similar business of the Corporation and shall be neutral and impartial. Each appraiser shall disclose to all parties any circumstances likely to affect his impartiality, including any bias, any financial or personal interest in the outcome of the appraisal, and any past or present relationship with any of the parties or their counsel. The Board of Directors, on the one hand, and the Objecting Shareholders, on the other hand, shall each be responsible for paying the fees of their respective appointed appraiser.

(C) Within seventy (70) days of appointment, each appraiser shall determine the fair market value of the business of the Corporation as of December 31st of the preceding year. Each appraiser shall deliver written notice of such fair market value to the Board of Directors and the Objecting Shareholders within such time period.

(D) In the event that the difference between the appraised values determined by each of the appraisers is ten percent (10%) or less, the fair market value of the business of the Corporation shall be determined by averaging the appraised value of each of the appraisers. In the event that only one appraiser has timely delivered notice of his/her appraised value, then such appraisal shall determine the fair market value of the business of the Corporation. In the event that the difference between the appraised values determined by each of the appraisers is greater than ten percent (10%), then a third appraiser shall be appointed by the original two appraisers within ten (10) days and the fair market value shall be determined by the majority vote of the three appraisers within ten (10) days of the most recent appraisal issued under subsection (iii) above; provided, however, that such appraised value shall be within the range of appraised values originally determined by the two appraisers under subsection (iii) above.

(3) At the closing of a redemption or purchase of a Redeemable Shareholder’s Shares pursuant to this Section 2(b), the Corporation or its assignee shall pay to the Redeemable Shareholder the Redemption Price in the following manner: one-third (1/3) by cashier’s check and two-thirds (2/3) pursuant to a promissory note (the “Redemption Note”). Fifty percent (50%) of the outstanding principal and interest due under the Redemption Note shall be payable on the first (1^st) anniversary of the closing and the balance thereof shall be payable on the second (2^nd) anniversary of the closing. The Redemption Note shall be reasonably satisfactory to the Corporation and the Redeemable Shareholder and shall bear simple interest at an annualized interest rate equal to the Prime Rate as published in the Wall Street Journal on the date of issuance of the Redemption Note.

(c) BCD Sale; Obtaining Offer. If BCD proposes to sell all or substantially all of its Shares in any single transaction or related series of transactions and other than to an Affiliate, then BCD shall cause the proposed purchaser to deliver to the Shareholders an offer to purchase all of their Shares on the same relative terms and conditions as offered to BCD for its Shares. The Shareholders may accept such additional offer by delivering their written acceptances to the proposed purchaser within thirty (30) days from the receipt of such offer from the proposed purchaser. The closing of any sale pursuant to this Section 2(c) shall occur simultaneously with the sale of BCD’s Shares to said purchaser.

(d) Mandatory Sale. If shareholders of the Corporation holding an aggregate of sixty percent (60%) or more of the Shares (“the Selling Shareholders”) agree to sell their

4

interests in the Corporation in any single transaction or related series of transactions other than to an Affiliate, and the proposed purchaser desires to acquire all the Shares in the Corporation, then all of the Shareholders shall sell their Shares to said proposed purchaser on the same relative terms and conditions contained in the offer delivered to the Selling Shareholders.

(e) Permitted Transfers by Brittin, Hopley, Smith and Siler. Each of the Shareholders may transfer their Shares to any one or more of their spouse, siblings, children or other lineal descendants, parents or lineal ancestors, or any trust created solely for the benefit of any one or more of such individuals; provided, however, that all such transferees shall, prior to such transfer, execute an attorney-in-fact (in form and substance reasonably satisfactory to the Corporation) in favor of the transferor for the purpose of exercising all rights, receiving notices and taking any action with respect to the Shares.

3. Conditions of Transfer. No Transfer of Shares, other than permitted transfers under Section 2(e), will be effectuated by the Corporation until the following conditions have been satisfied:

(a) The written consent of the Board of Directors must have been obtained;

(b) the transferee must have executed a written agreement, in form and substance satisfactory to the Board of Directors, to assume all of the duties and obligations of the transferor Shareholder under this Agreement and to be bound by and subject to all of the terms and conditions of this Agreement;

(c) the transferee or transferor must have paid the expenses incurred by the Corporation in connection with the Transfer;

(d) upon request of the Corporation, the transferor must have delivered to the Corporation a written opinion of counsel reasonably satisfactory to the Board of Directors (which opinion shall be obtained at the expense of the transferor) that such Transfer will not result in a violation of applicable law including the Securities Act of 1933, as amended (the “Securities Act”), or any applicable state securities laws, or of this Agreement;

(e) the transferor must have executed a written instrument of transfer of Shares in form and substance satisfactory to the Board of Directors; and

(f) the transferor and the transferee must have executed a written agreement, in form and substance satisfactory to the Board of Directors, to indemnify and hold the Corporation and all shareholders of the Corporation harmless from and against any loss or liability arising out of the Transfer.

4. Term. This Agreement shall terminate immediately upon the occurrence of any of the following events:

(a) The bankruptcy, receivership, insolvency or dissolution of the Corporation;

5

(b) The unanimous written agreement of the Shareholders and consent of the Corporation;

(c) The cessation of the Corporation’s business; or

(d) The effective date of the filing of a registration statement by the Corporation with the Securities and Exchange Commission with respect to an initial public offering of its securities.

5. Piggy-Back Registration Rights. If the Corporation allows the inclusion of any Shares held by a shareholder in a public offering registered under the Securities Act of 1933, as amended, the Shareholders shall be entitled to include their Shares in such offering on a pro rata basis, provided that the aggregate amount to be included shall be at the discretion of the Corporation and the managing underwriter. In order to participate in the offering, each Shareholder must provide such information and execute such agreements and other documents as may be required of selling shareholders in the offering by the Corporation and the managing underwriter.

6. Specific Enforcement. Each Shareholder expressly agrees that the Shares cannot be purchased or sold in the public market and that for these reasons, among others, the Corporation and the other Shareholders would be irreparably damaged if this Agreement is not specifically enforced. Upon a breach or threatened breach of the terms, covenants and/or conditions of this Agreement by any Shareholder, the Corporation shall, in addition to all other remedies, be entitled to a temporary or permanent injunction, and/or a decree for specific performance, in accordance with the provisions hereof, without the necessity of proof of actual damages or the posting of a bond or other security.

7. Legend.

(a) During the term of this Agreement, each certificate evidencing any of the Shares now owned or hereafter acquired by the Shareholders shall bear a legend substantially as follows:

“Any sale, assignment, transfer or other disposition of the shares represented by this certificate is restricted by, and subject to, the terms and provisions of a certain Shareholders Agreement dated as of November 4, 1999, as it may be amended or restated from time to time. A copy of said Agreement is on file with the Secretary of the Corporation.”

6

(b) The undersigned understands and acknowledges that the Shares have not been registered for sale under the Securities Act or any applicable state securities laws and that the Shares will be issued and sold by the Corporation in reliance upon exemptions from the registration requirements of such acts. Accordingly, the undersigned understands and agrees that for a period of at least one year from the date of issuance of the Shares, (i) stop-transfer instructions will be noted on the appropriate records of the Corporation and (ii) there will be maintained on the certificate(s) evidencing the Shares, or any substitutions therefor, a legend reading as follows:

THE SHARES EVIDENCED BY THIS CERTIFICATE HAVE NOT BEEN REGISTERED FOR SALE UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE “SECURITIES ACT”), OR ANY OTHER STATE SECURITIES LAWS (COLLECTIVELY, THE “STATE SECURITIES ACTS”), AND HAVE BEEN ISSUED AND SOLD IN RELIANCE UPON EXEMPTIONS FROM THE REGISTRATION REQUIREMENTS OF SUCH ACTS, INCLUDING, BUT NOT NECESSARILY LIMITED TO, THE EXEMPTIONS CONTAINED IN SECTION 4(2) OF THE SECURITIES ACT. THESE SECURITIES MAY NOT BE SOLD OR TRANSFERRED EXCEPT PURSUANT TO AN EFFECTIVE REGISTRATION STATEMENT OR IN A TRANSACTION WHICH IS EXEMPT FROM REGISTRATION UNDER THE SECURITIES ACT, AND ALL APPLICABLE STATE SECURITIES ACTS.

Any assignment or endorsement of the certificate(s) representing the Shares which is in violation of the restrictions on transfer provided above will not be recognized by the Corporation nor will any assignee or endorsee of such shares be recognized as the owner thereof by the Corporation.

8. Notices. All notices, designations, consents, offers or any other communications provided for in this Agreement must be given in writing, personally delivered, by a recognized overnight mail and courier service or by mail. If by mail, it must be mailed by registered or certified mail, postage prepaid, return receipt requested, and it will be deemed to have been given on the date which is three (3) days following the date it is posted. Notice to the Corporation is to be addressed to its then principal office. Notices to the Shareholders are to be addressed to their respective addresses as they appear on the transfer books of the Corporation, or to such other address as may be designated by a Shareholder in writing to the Secretary of the Corporation.

9. Entire Agreement. This Agreement constitutes the entire agreement among the Shareholders and the Corporation with respect to the subject matter hereof and supersedes all prior agreements and understandings between them or any of them with respect to such subject matter. The Original Agreement is of no further force or effect.

10. Governing Law. Successors and Assigns. This Agreement shall be governed by, and construed and enforced in accordance with the laws of the State of Georgia (without giving effect to the conflict of law principles thereof).

11. Severability. If any provision of this Agreement shall be held to be illegal, invalid or unenforceable, such illegality, invalidity or unenforceability shall attach only to such provision and shall not in any manner affect or render illegal, invalid or unenforceable any other provision of this Agreement, and this Agreement shall be earned out as if any such illegal, invalid or unenforceable provision were not contained herein.

12. Captions and Headings. Captions and Article and Section headings are for convenience only and are not deemed to be part of this Agreement, and in no way define, limit, extend or describe the scope of this Agreement or the intent of any provision hereof.

7

13. Singular and Plural. Etc. Whenever the singular number is used herein and where required by the context, the same shall include the plural, and the neuter gender shall include the masculine and feminine genders.

14. Amendments and Waivers. This Agreement and any term hereof may only be changed, waived, discharged or terminated in writing only with the written consent of the Corporation and the shareholders holding at least 80% of the common stock of the Corporation then owned by the parties to this Agreement (the “Amending Shareholders”). Notwithstanding the preceding sentence, no waiver shall extend to or affect any other obligation not expressly waived and no amendments to this Agreement shall be made which materially and negatively impact the rights of the non-Amending Shareholders without also obtaining the approval of such non-Amending Shareholders; provided, however, that it is expressly contemplated that this Agreement may be amended without a vote of the non-Amending Shareholders so long as the rights of the non-Amending Shareholders are not adversely affected in a manner which is materially different than the manner in which the rights of the Amending Shareholders are affected. No failure to exercise and no delay in exercising, on the part of any party, any right, remedy, power or privilege hereunder shall operate as a waiver thereof; nor shall any single or partial exercise of any right, remedy, power or privilege hereunder preclude any other or further exercise thereof or the exercise of any other right remedy, power or privilege. The rights, remedies, powers and privileges herein provided are cumulative and not exclusive of any rights, remedies, powers and privileges provided by law. The failure of any party to insist upon a strict performance of any of the terms or provisions of this Agreement, or to exercise any option, right or remedy herein contained, shall not be construed as a waiver or as a relinquishment for the future of such term, provision, option, right or remedy, but the same shall continue and remain in full force and effect.

15. Successors and Assigns. All rights, covenants and agreements of the parties contained in this Agreement shall, except as otherwise provided herein, be binding upon and inure to the benefit of their respective successors and assigns.

16. Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original, but all of which together shall constitute one and the same instrument.

(Signatures for this Amended and Restated Shareholders Agreement

appear on following page)

8

IN WITNESS WHEREOF, this Agreement has been executed as of the day and year first above written.

(Signature page to the Amended and Restated Shareholders Agreement)