NEUTRAL TANDEM, INC. SECONDAMENDED AND RESTATED REGISTRATION RIGHTS AGREEMENT

EXHIBIT 4.5

NEUTRAL TANDEM, INC.

SECOND AMENDED AND RESTATED REGISTRATION RIGHTS AGREEMENT

This SECOND AMENDED AND RESTATED REGISTRATION RIGHTS AGREEMENT (this “Agreement”) is entered into as of February 2, 2006, by and among Neutral Tandem, Inc., a Delaware corporation (the “Company”), the individuals and entities listed on Schedule 1 hereto (the “Investors”), and the existing stockholders of the Company listed on Schedule 2 hereto (the “Common Holders”, and, collectively with the Investors, the “Stockholders”)

RECITALS:

WHEREAS, the Company and certain of the Stockholders are parties to an Amended and Restated Registration Rights Agreement dated as of November 19, 2004 (the “First Amended and Restated Agreement”);

WHEREAS, the Company and certain of the Investors have entered into a Stock Purchase Agreement, dated as of the date hereof (as the same may be amended, modified or supplemented from time to time, the “Purchase Agreement”) providing for the issuance, delivery and sale of shares of the Company’s Series C Preferred; and

WHEREAS, in order to induce the Investors to purchase shares of Series C Preferred pursuant to and as provided in the Purchase Agreement, the Company has agreed to register the shares of Common Stock issued or issuable upon conversion of the Series C Preferred upon the terms set forth herein and it is a condition to the closing of the Purchase Agreement that this Agreement be executed and delivered by the parties hereto;

NOW, THEREFORE, in consideration of the mutual promises, covenants and conditions set forth herein, and for other good and valuable consideration the receipt and adequacy of which are hereby acknowledged, the parties hereby agree as follows:

Section 1. Demand Registration.

(a) Request for Registration. At any time beginning six (6) months following the Company’s IPO, Investors holding not less than 30% of the issued and outstanding shares of Preferred Stock may request registration under the Securities Act of all or part of their Registrable Securities (i) on Form S 1 or any successor form (an “S-1 Registration”), so long as any such S-1 Registration is for not less than an aggregate offering price of $10,000,000, and (ii) on Form S 3 or any similar short form registration (an “S-3 Registration” and, together with an S-1 Registration, a “Demand Registration”), if the Company is eligible to use such form, so long as any such S-3 Registration is for not less than an aggregate price to the public of $1,000,000. A request for registration pursuant to this Section 1 shall specify the approximate number of Registrable Securities requested to be registered and the anticipated per share price range for such offering. Within ten (10) days after receipt of any such request, the Company shall give written notice of such requested registration, and any related qualification or compliance, to all Investors and shall include in such registration all Registrable Securities with respect to which the Company has received from the Investors written requests for inclusion therein within fifteen

(15) days after the receipt of the Company’s notice. The Company shall use its commercially reasonable efforts to effect the Demand Registration under the Securities Act as promptly as practicable of all Registrable Securities requested to be registered, subject to the limitations of Sections 1(c) and 6 hereof.

(b) Registration Statement Form. Demand Registrations under this Section 1 shall be on such appropriate registration form of the Commission as shall be selected by the Investors and available under the Securities Act for the Company. The Company agrees to include in any such registration statement all information which, in the opinion of counsel to the Investors participating in such registration (the “Participating Investors”) and counsel to the Company, is required to be included therein under the Securities Act.

(c) Limitations on Registration; Expenses.

(i) The Company shall not be required to effect more than two S-1 Registrations.

(ii) The Company shall not be required to effect more than two S-3 Registrations during any calendar year.

(iii) The Company shall bear the Registration Expenses with respect to each Demand Registration. Notwithstanding the foregoing, if any request for a Demand Registration is withdrawn or terminated by the request of two-thirds of the Registrable Securities held by the Participating Investors prior to the effectiveness of such Demand Registration, the Registration Expenses incurred in connection with such request shall be borne by the Participating Investors, pro rata based on the percentage of the aggregate number of Registrable Securities of Participating Investors registered pursuant to such registration which are represented by the Registrable Securities of each Participating Investor included therein; provided, however, that if the Participating Investors holding two-thirds of the Registrable Securities pursuant to the withdrawn or terminated registration so request such Registration Expenses shall be borne by the Company and such Demand Registration will reduce the number then available to the Investors and shall count as one Demand Registration; provided, however, that if at the time of such withdrawal, the Participating Investors have learned of a material adverse change in the condition, business or prospects of the Company from that known to the Participating Investors at the time of their request and have withdrawn the request with reasonable promptness following disclosure by the Company of such material adverse change, then the Participating Investors shall not be required to pay any of such expenses and shall retain their rights pursuant to Section 1.

(iv) If, prior to the time of any request by Investors pursuant to Section 1(a), the Company has publicly announced its intention to register any of its securities for a public offering under the Securities Act, no registration of Registrable Securities shall be initiated pursuant to Section 1(a) until one hundred eighty (180) days after the effective date of a Company-initiated registration so announced unless the Company is no longer proceeding diligently to effect such registration.

(v) No request shall be made under Section 1(a) within one hundred eighty (180) days after the effective date of a registration statement filed by the Company covering an underwritten public offering in which Investors shall have been entitled to participate pursuant to Section 2 hereof.

(d) Effective Registration Statement. Subject to the provisions of Section 1(e) below and the proviso to Section 1(c)(iii) above, a Demand Registration shall not be deemed to have been

- 2 -

effected (i) unless a registration statement with respect thereto has become effective, (ii) if after it has become effective, such registration is interfered with by any stop order, injunction or other order or requirement of the Commission or other governmental agency or court for any reason not attributable to the Participating Investors and has not thereafter become effective, or (iii) if the conditions to closing specified in the underwriting agreement, if any, entered into in connection with such registration are not satisfied or waived, other than by reason of a failure on the part of the Participating Investors.

(e) Certain Other Matters.

(i) For purposes of clause (i) of Section 1(d) above, should a Demand Registration not become effective because of the failure of the Participating Investors to perform their obligations under this Agreement or in the event the Participating Investors withdraw or do not pursue the request for the Demand Registration (in each of the foregoing cases, provided that at such time the Company is in compliance with its obligations under this Agreement), then such Demand Registration shall be deemed to have been effected.

(ii) Under the circumstances in which a Demand Registration otherwise would be deemed to have been effected under Section 1(d) above (including as contemplated by this Section 1(e)), if the Participating Investors pay the Registration Expenses (other than the Registration Expenses referred to in clause (i) of the definition of Registration Expenses contained in Section 12 hereof) incurred by the Company through the date of abandonment of the registration, the Demand Registration shall not be deemed to have been effected for purposes of Section 1(d) of this Agreement; provided, however, that if on the date of abandonment of the registration a preliminary prospectus related to the Demand Registration has not been filed with the Commission, then (x) the Participating Investors may elect to delay payment of such Registration Expenses for six (6) months following the date of such abandonment, and (y) at any time during such six-month period, the Participating Investors shall be entitled to reactivate the abandoned registration, in which case the reactivated registration and abandoned registration shall be deemed to be one registration, and the Participating Investors shall not be required to pay any Registration Expenses associated therewith, except as provided in Section 1(c) above.

(f) Certain Exclusions. The Company shall not include in any Demand Registration any securities of the Company not held by an Investor that has complied with the requirements of Section 1, without the prior written consent of the Participating Investors holding at least two-thirds of the Registrable Securities requested to be included in such registration.

Section 2. Company Registration.

(a) Inclusion in Company Registration. If (but without any obligation to do so) the Company proposes at any time to register (including for this purpose a registration effected by the Company for stockholders other than the Investors) any of its stock or other securities under the Securities Act in connection with the public offering of such securities solely for cash (other than a registration (i) relating solely to the sale of securities to participants in a Company stock plan, (ii) on Form S 4 (or successor form) with respect to any merger, consolidation or acquisition, (iii) on any form which does not include substantially the same information as would be required to be included in a registration statement covering the sale of the Registrable Securities, or (iv) in which the only Common Stock being registered is Common Stock issuable upon conversion of debt securities which are also being registered), then the Company shall, at such time, promptly give each Stockholder written notice of such registration. Upon the written request of each Stockholder given within twenty (20) days after mailing of such notice by the Company in accordance with Section 13(e), the Company shall, subject to the provisions of Section 6, use

- 3 -

its commercially reasonable efforts to cause to be registered under the Securities Act all of the Registrable Securities that each such Stockholder has requested to be registered.

(b) Registration Expenses in Company Registration. The Company shall pay the Registration Expenses in connection with any Company registration pursuant to Section 2(a) above.

(c) Company’s Right to Withdraw Registration. Notwithstanding the foregoing provisions, the Company may withdraw any registration statement referred to in this Section 2 without thereby incurring any liability to the Stockholders.

Section 3. Company’s Right to Postpone or Delay Registration. For a period not to exceed an aggregate of one hundred twenty (120) days within any one-year period, the Company shall not be obligated to prepare and file, or be prevented from delaying, a registration statement pursuant to this Agreement at any time when the Company, in its good faith judgment with advice of counsel and after notifying all Stockholders requesting participation in such registration, reasonably believes:

(a) that the filing thereof at the time requested, or the offering of Registrable Securities pursuant thereto, would materially and adversely affect (i) a pending or scheduled public offering of the Company’s securities, (ii) an acquisition, merger, recapitalization, consolidation, reorganization or similar transaction by or of the Company, (iii) pre-existing negotiations, discussions or pending proposals with respect to any of the foregoing transactions, or (iv) the financial condition of the Company in view of the disclosures of any pending or threatened litigation, claim, assessment or governmental investigation which may be required thereby; and

(b) that the failure to disclose any material information with respect to the foregoing would in the Company’s good faith judgment be reasonably likely to cause a violation of the Securities Act.

Notwithstanding anything to the contrary contained in this Section 3, in connection with a delay or postponement as contemplated by this Section 3, (i) the Company shall furnish to all Stockholders requesting participation in such registration with a certificate signed by the Company’s Chief Executive Officer or Chairman of the Board stating that in the good faith judgment of the Board of Directors of the Company, it would be seriously detrimental to the Company and its stockholders for such registration statement to be effected at such time, and (ii) the Company shall not be entitled to delay or postpone registration pursuant to Section 3 unless during such period of delay or postponement all executive officers and directors of the Company are also prohibited from selling securities of the Company (or any security of any of the Company’s subsidiaries or affiliates).

Section 4. Obligations of the Company. Whenever required under this Agreement to effect the registration of any Registrable Securities under this Agreement, the Company shall, as expeditiously as reasonably possible:

(a) Prepare and file with the Commission a registration statement with respect to such Registrable Securities and use its commercially reasonable efforts to cause such registration statement to become effective, and keep such registration statement effective for up to nine (9) months in the case of an S-1 Registration, or twelve (12) months in the case of an S-3 Registration (or one hundred twenty (120) days in the case of any registration statement pursuant to which shares of Common Stock are being offered for the account of the Company), or, if occurring sooner, until the date on which the distribution of the Registrable Securities shall be completed.

- 4 -

(b) Prepare and file with the Commission such amendments and supplements to such registration statement and the prospectus used in connection with such registration statement as may be necessary to comply with the provisions of the Securities Act with respect to the disposition of all securities covered by such registration statement, provided that such period need not extend beyond one year after the effective date of the registration statement.

(c) Furnish to the Stockholders participating in such registration such number of copies of a prospectus, including a preliminary prospectus, in conformity with the requirements of the Securities Act, and such other documents as they may reasonably request in order to facilitate the disposition of Registrable Securities owned by them.

(d) Use its commercially reasonable efforts to register and qualify the securities covered by such registration statement under such other securities or Blue Sky laws of such jurisdictions as shall be reasonably requested by the Stockholders participating in such registration, provided that the Company shall not be required in connection therewith or as a condition thereto to qualify to do business or to file a general consent to service of process in any such states or jurisdictions.

(e) In the event of any underwritten public offering, enter into and perform its obligations under an underwriting agreement, in usual and customary form, with the managing underwriter of such offering.

(f) Notify each Stockholder of Registrable Securities covered by such registration statement at any time when a prospectus relating thereto is required to be delivered under the Securities Act of the happening of any event that results in such prospectus including an untrue statement of a material fact or omits to state a material fact required to be stated therein or necessary to make the statements therein not misleading in the light of the circumstances then existing.

(g) Use its commercially reasonable efforts to furnish, at the request of any Stockholder participating in such registration, on the date that such Stockholder’s Registrable Securities covered by such registration are delivered to the underwriters for sale in connection with a registration pursuant hereto, if such securities are being sold through underwriters, or, if such securities are not being sold through underwriters, on the date that the registration statement with respect to such securities becomes effective, (i) an opinion, dated such date, of counsel representing the Company for the purposes of such registration, in form and substance as is customarily given to underwriters in an underwritten public offering, addressed to the underwriters, if any, and to such Stockholder, and (ii) a letter dated such date, from the independent certified public accountants of the Company, in form and substance as is customarily given by independent certified public accountants to underwriters in an underwritten public offering, addressed to the underwriters, if any, and to such Stockholder.

(h) Cause all such Registrable Securities registered to be listed on each securities exchange on which similar securities issued by the Company are then listed.

(i) Provide a transfer agent and registrar for all Registrable Securities registered and a CUSIP number for all such Registrable Securities, in each case not later than the effective date of such registration.

Section 5. Certain Obligations of Stockholders.

(a) It shall be a condition precedent to the obligations of the Company to take any action under this Agreement with respect to the Registrable Securities of any Stockholder participating in any registration that such Stockholder (i) furnish to the Company such information regarding itself, the

- 5 -

Registrable Securities held by it, and the intended method of disposition of such securities as shall be required to effect the registration of such Stockholder’s Registrable Securities, and (ii) in the event of an underwritten offering, enter into and perform its obligations under the underwriting agreement associated therewith.

(b) Each Stockholder of Registrable Securities covered by a registration statement agrees that, upon receipt of any notice from the Company under Section 4(f) hereof, such Stockholder will forthwith discontinue disposition of Registrable Securities pursuant to such registration statement until such Stockholder’s receipt of copies of a supplemented or amended prospectus covering such Registrable Securities, and, if so directed by the Company, such Stockholder will deliver to the Company (at the Company’s expense) all copies, other than permanent file copies then in such Stockholder’s possession, of the prospectus covering such Registrable Securities current at the time of its receipt of such notice.

(c) The Company shall have no obligation with respect to any registration requested pursuant to Section 1 or Section 2 if, due to the operation of Section 5(a), the number of shares or the anticipated aggregate offering price of the Registrable Securities to be included in the registration does not equal or exceed the number of shares or the anticipated aggregate offering price required to originally trigger the Company’s obligation to initiate such registration as specified in Section 1 or Section 2, whichever is applicable.

Section 6. Underwriting Requirements.

(a) If the Investors initiating a registration request pursuant to Section 1 (the “Initiating Investors”) intend to distribute the Registrable Securities covered by their request by means of an underwriting, (i) the Initiating Investors shall so advise the Company as part of their request made pursuant to Section 1(a), and the Company shall include such information in its written notice to Investors referred to in Section 1(a), and (ii) the underwriter shall be reasonably acceptable to the Participating Investors holding at least two-thirds of the Registrable Securities requested to be included in such registration.

(b) In connection with any offering involving an underwriting of shares of the Company’s capital stock, the Company shall not be required under Section 2 to include any Stockholder’s securities in such underwriting unless such Stockholder accepts the terms of the underwriting as agreed upon between the Company and the underwriters selected by it (or by other persons entitled to select the underwriters).

(c) In connection with an underwritten Demand Registration, if the managing underwriter of such underwriting shall have informed the Company (which shall distribute such notice to the Participating Investors and any other participating stockholders) by letter of its belief that the inclusion in such underwritten distribution of all or a specified number of such Registrable Securities or of other securities so requested to be included would interfere with the successful marketing of the securities by the underwriters (such writing to state the basis of such belief and the approximate number of Registrable Securities and other securities so requested to be included which may be included in such underwritten offering without such effect, if any), then the Company may (i) first exclude from such registration all securities sought to be included therein by holders of the Company’s securities other than the Participating Investors, and then, (ii) upon written notice to all Participating Investors, exclude from such underwritten offering (if and to the extent stated by such managing underwriter to be necessary) the number of Registrable Securities requested to be included by each Participating Investor so that the resultant aggregate amount of securities so included in such offering shall be equal to the amount stated in such managing underwriter’s letter, pro rata based on the percentage of the aggregate number of Registrable Securities of Participating Investors requested to be registered which are represented by the

- 6 -

number of Registrable Securities requested by such Participating Investor to be included therein (or in such other proportions as shall mutually be agreed to by the Participating Investors).

(d) In connection with an underwritten registration pursuant to Section 2 hereof, if the managing underwriter of such underwriting shall have informed the Company (which shall distribute such notice to the Stockholders participating Investors and any other participating stockholders) by letter of its belief that the inclusion in such underwritten distribution of all or a specified number of such Registrable Securities or of other securities so requested to be included would interfere with the successful marketing of the securities by the underwriters (such writing to state the basis of such belief and the approximate number of Registrable Securities and other securities so requested to be included which may be included in such underwritten offering without such effect, if any), then the Company may (i) first exclude from such registration all securities sought to be included therein by holders of the Company’s securities other than the Stockholders, and then, (ii) upon written notice to all Stockholders, exclude from such underwritten offering (if and to the extent stated by such managing underwriter to be necessary) the number of Registrable Securities requested to be included by each Stockholder so that the resultant aggregate amount of such securities so included in such offering shall be equal to the amount stated in such managing underwriter’s letter, pro rata based on the percentage of the aggregate number of Registrable Securities of participating Stockholders requested to be registered which are represented by the number of Registrable Securities requested by such Stockholder to be included therein (or in such other proportions as shall mutually be agreed to by such participating Stockholders); provided, however, that without the prior written consent of the Investors holding at least two-thirds of the Registrable Securities requested by Investors to be included in such registration, in no event shall the number of Registrable Securities requested to be included by Investors in such offering be reduced below 30% of the total number of Registered Securities requested to be included by Investors, unless such offering is the Company’s IPO, in which event no such limitation shall apply and the Company may exclude all of the securities any Stockholder requests to be included in such registration.

Section 7. Indemnification. In the event any Registrable Securities are included in a registration statement under this Agreement:

(a) To the extent permitted by law, the Company will indemnify and hold harmless each Stockholder, its officers, directors, stockholders and partners, any underwriter (as defined in the Securities Act), legal counsel and accountants for such Stockholder and each person, if any, who controls such Stockholder or underwriter within the meaning of the Securities Act or the Exchange Act, against any losses, claims, damages, or liabilities (joint or several) to which they may become subject under the Securities Act or the Exchange Act or other federal or state law, insofar as such losses, claims, damages, or liabilities (or actions in respect thereof) arise out of or are based upon any of the following statements, omissions or violations (any of the following a “Violation”): (i) any untrue statement or alleged untrue statement of a material fact contained in such registration statement, including any preliminary prospectus or final prospectus contained therein or any amendments or supplements thereto, (ii) the omission or alleged omission to state therein a material fact required to be stated therein, or necessary to make the statements therein not misleading, or (iii) any violation or alleged violation by the Company of the Securities Act, the Exchange Act, any state securities law or any rule or regulation promulgated under the Securities Act, or the Exchange Act or any state securities law in connection with the offering covered by such registration statement; and the Company will pay to each such Stockholder, officer, director, stockholder, partner, underwriter, legal counsel, accountant or controlling person any legal or other expenses as reasonably incurred by them in connection with investigating or defending any such loss, claim, damage, liability, or action; provided, however, that the Company shall not be liable (x) in any such case for any such loss, claim, damage, liability, or action to the extent that it arises out of or is based upon a Violation which occurs in reliance upon and in conformity with written information furnished expressly for use in connection with such registration by any such Stockholder, underwriter or controlling

- 7 -

person, or (y) in the case of a sale directly by such Stockholder (including a sale of such Registrable Securities through any underwriter retained by such Stockholder to engage in a distribution solely on behalf of such Stockholder), such Violation was contained in a preliminary prospectus and corrected in a final or amended prospectus, and such Stockholder failed to deliver a copy of the final or amended prospectus at or prior to the confirmation of the sale of the Registrable Securities to the person asserting any such loss, claim, damage, liability or action in any case where such delivery is required by the Securities Act or any state securities laws.

(b) To the extent permitted by law, each Stockholder participating in such registration will indemnify and hold harmless the Company, each of its directors, each of its officers who has signed the registration statement, each person, if any, who controls the Company within the meaning of the Securities Act, any underwriter, any other Stockholder selling securities in such registration statement and any controlling person of any such underwriter or other Stockholder, and legal counsel and accountants for the Company and each such other person against any losses, claims, damages, or liabilities (joint or several) to which any of the foregoing persons may become subject, under the Securities Act, or the Exchange Act or other federal or state law, insofar as such losses, claims, damages, or liabilities (or actions in respect thereto) arise out of or are based upon any Violation, in each case to the extent (and only to the extent) that such Violation occurs in reliance upon and in conformity with written information furnished by such Stockholder expressly for use in connection with such registration; and each such Stockholder will pay any legal or other expenses as reasonably incurred by any person intended to be indemnified pursuant to this Section 7(b), in connection with investigating or defending any such loss, claim, damage, liability, or action; provided, however, that the indemnity contained in this Section 7(b) shall not apply to amounts paid in settlement of any such loss, claim, damage, liability, or action if such settlement is effected without the consent of such Stockholder, which consent shall not be unreasonably withheld or delayed; provided further, that, in no event shall any indemnity under this Section 7(b) exceed the net proceeds from the offering actually received by such Stockholder.

(c) Promptly after receipt by an indemnified party under this Section 7 of notice of the commencement of any action (including any governmental action), such indemnified party will, if a claim in respect thereof is to be made against any indemnifying party under this Section 7, deliver to the indemnifying party a written notice of the commencement thereof and the indemnifying party shall have the right to participate in, and, to the extent the indemnifying party so desires, jointly with any other indemnifying party similarly noticed, to assume the defense thereof with counsel mutually satisfactory to the parties; provided, however, that an indemnified party (together with all other indemnified parties which may be represented without conflict by one counsel) shall have the right to retain one separate counsel, with the reasonable fees and expenses to be paid by the indemnifying party, if representation of such indemnified party by the counsel retained by the indemnifying party would be inappropriate due to actual or potential differing interests between such indemnified party and any other party represented by such counsel in such proceeding. The failure to deliver written notice to the indemnifying party within a reasonable time of the commencement of any such action, if prejudicial to its ability to defend such action, shall relieve such indemnifying party of any liability to the indemnified party under this Section 7, but the omission so to deliver written notice to the indemnifying party will not relieve it of any liability that it may have to any indemnified party otherwise than under this Section 7.

(d) If the indemnification provided for in this Section 7 is held by a court of competent jurisdiction to be unavailable to an indemnified party with respect to any loss, liability, claim, damage, or expense referred to therein, then the indemnifying party, in lieu of indemnifying such indemnified party hereunder, shall contribute to the amount paid or payable by such indemnified party as a result of such loss, liability, claim, damage, or expense in such proportion as is appropriate to reflect the relative fault of the indemnifying party on the one hand and of the indemnified party on the other in connection with the statements or omissions that resulted in such loss, liability, claim, damage, or expense

- 8 -

as well as any other relevant equitable considerations. The relative fault of the indemnifying party and of the indemnified party shall be determined by reference to, among other things, whether the untrue or alleged untrue statement of a material fact or the omission to state a material fact relates to information supplied by the indemnifying party or by the indemnified party, and the parties’ relative intent, knowledge, access to information, and opportunity to correct or prevent such statement or omission; provided, however, that, in any such case, (i) no Stockholder will be required to contribute any amount in excess of the net proceeds from the offering received by such Stockholder; and (ii) no person or entity guilty of fraudulent misrepresentation (within the meaning of Section 11(f) of the Securities Act) will be entitled to contribution from any person or entity who was not guilty of such fraudulent misrepresentation.

(e) Notwithstanding the foregoing, to the extent that the provisions on indemnification and contribution contained in the underwriting agreement entered into in connection with the underwritten public offering are in conflict with the foregoing provisions, the provisions in the underwriting agreement shall control.

(f) The obligations of the Company and Stockholders under this Section 7 shall survive the completion of any offering of Registrable Securities pursuant to a registration statement under this Agreement, and otherwise.

Section 8. Reports Under Exchange Act. With a view to making available to the Stockholders the benefits of Rule 144 promulgated under the Securities Act and any other rule or regulation of the Commission that may at any time permit a Stockholder to sell securities of the Company to the public without registration or pursuant to a registration on Form S-3, the Company agrees to:

(a) make and keep public information available, as those terms are understood and defined in Rule 144 under the Securities Act, at all times after the effective date of the first registration statement filed by the Company for the offering of its securities to the general public;

(b) file with the Commission in a timely manner all reports and other documents required of the Company under the Securities Act and the Exchange Act; and

(c) furnish to any Stockholder, so long as such Stockholder owns any Registrable Securities, forthwith upon request (i) a written statement by the Company that it has complied with the reporting requirements of Rule 144 under the Securities Act (at any time following the 90th day after the effective date of the first registration statement filed by the Company), the Securities Act and the Exchange Act (at any time after it has become subject to such reporting requirements), or that the Company qualifies as a registrant whose securities may be resold pursuant to Form S-3 (at any time after it so qualifies), (ii) a copy of the most recent annual or quarterly report of the Company and such other reports and documents so filed by the Company, and (iii) such other information as may be reasonably requested in availing any Stockholder of any rule or regulation of the Commission which permits the selling of any such securities without registration or pursuant to such form.

Section 9. Transfer of Registration Rights. The registration rights of any Stockholder under this Agreement may be transferred; provided, however, that the Company is given written notice from such Stockholder at the time of such transfer stating the name and address of the transferee and identifying the securities with respect to which the rights hereunder are being transferred. As a condition to the effectiveness of any such transfer, (i) the transferee shall agree in writing, upon request of the Company, to be bound by the provisions of this Agreement and (ii) the Company shall be given written notice at the time of or within a reasonable time after said transfer, stating the name and address of said transferee or assignee and identifying the securities with respect to which such registration rights are

- 9 -

being transferred or assigned, and (iii) the transferee acquires at least 20% of the Registrable Securities held by the transferor; provided, however, that such minimum shall not apply to Affiliates, as defined in the Purchase Agreement.

Section 10. Lock-Up Agreement.

(a) Each Stockholder hereby agrees that, during a period (not to exceed one hundred eighty (180) days) specified by the Company and an underwriter of Common Stock or other securities of the Company, following the effective date of a registration statement filed by the Company under the Securities Act, it shall not, to the extent requested by the Company and such underwriter, directly or indirectly sell, offer to sell, contract to sell (including, without limitation, any short sale), grant any option to purchase or otherwise transfer or dispose of (other than to donees who agree to be similarly bound) any securities of the Company held by it at any time during such period except Common Stock included in such registration; provided, however, that all officers and directors of the Company and all other persons with registration rights (whether or not pursuant to this Agreement) enter into similar agreements; and provided, further, that such lock-up agreement made by the Investors shall apply only to the Company’s IPO and shall not apply to any Common Stock (or other securities) of the Company acquired by the Investors in connection with or following the Company’s IPO (the forgoing proviso may not be amended as to any Investor without the written consent of such Investor).

(b) In order to enforce the foregoing covenant, the Company may impose stop-transfer instructions with respect to the Registrable Securities of each Stockholder (and the shares or securities of every other person subject to the foregoing restriction) until the end of such period.

Section 11. Termination of Registration Rights. The obligations of the Company hereunder shall terminate with respect to each Stockholder on, and no Stockholder shall be entitled to exercise any right provided hereunder after, the first to occur of (i) the date that is the 5th anniversary of the consummation of the Company’s IPO, or (ii) the date on which such Stockholder may sell, transfer or dispose of the Registrable Securities held by it or him without regard to provisions of Rule 144 under the Securities Act concerning volume limitations, notice and manner of sale and public availability of information.

Section 12. Definitions.

(a) Capitalized terms used herein without definition shall have the meanings assigned to such terms in the Purchase Agreement.

(b) For the purposes of this Agreement:

“Commission” means the Securities and Exchange Commission or any other governmental authority from time to time administering the Securities Act.

“Common Stock” means the shares of Common Stock, par value $0.001 per share, of the Company.

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

“IPO” means the initial underwritten public offering of shares of Common Stock pursuant to an effective registration statement.

- 10 -

“Preferred Stock” means the Company’s shares of Series A Preferred, Series B-1 Preferred, Series B-2 Preferred and Series C Preferred.

“Register,” “registered,” and “registration” refer to a registration effected by preparing and filing a registration statement or similar document in compliance with the Securities Act, and the declaration or ordering of effectiveness of such registration statement or document.

“Registrable Securities” means (i) the Common Stock issuable or issued upon conversion of any of the Company’s shares of Preferred Stock, (ii) any securities of the Company issued as (or issuable upon the conversion or exercise of any warrant, rights or other security which is issued as) a dividend or other distribution with respect to, or in exchange for or in replacement of, the securities referred to in clause (i), (iii) the Common Stock held by the Stockholders. As to any particular Registrable Securities, such securities shall cease to be Registrable Securities when (a) a registration statement with respect to the sale of such securities shall have become effective under the Securities Act and such securities shall have been transferred in accordance with such registration statement, (b) they shall have been sold as permitted by Rule 144 (or any successor provision) under the Securities Act, or (c) they shall have ceased to be outstanding.

“Registration Expenses” means all expenses incident to the Company’s performance of or compliance with Sections 1 or 2, including, without limitation, (i) any allocation of salaries and expenses of Company personnel or other general overhead expenses of the Company, or other expenses for the preparation of historical and pro forma financial statements or other data normally prepared by the Company in the ordinary course of business; (ii) all registration, application, filing, listing, transfer and registrar fees; (iii) all NASD fees and fees and expenses of registration or qualification of Registrable Securities under state securities or Blue Sky laws; (iv) all word processing, duplicating and printing expenses, messenger and delivery expenses; (v) the fees and disbursements of counsel for the Company and of its independent public accountants, including the expenses of customary “cold comfort” letters required by or incident to such performance and compliance; (vi) any fees and disbursements of underwriters and broker-dealers customarily paid by issuers or sellers of securities; and (vii) reasonable fees and expenses of one counsel to the Stockholders participating in such registration; provided, however, that in all cases in which the Company is required to pay Registration Expenses hereunder, Registration Expenses shall exclude, and the sellers of the Registrable Securities being registered shall pay, the fees and disbursements of more than one counsel to such sellers, underwriting discounts and commissions and transfer taxes in respect of the Registrable Securities being registered, and expenses of registering or qualifying Registrable Securities under state securities or Blue Sky laws, to the extent such laws prohibit the Company from paying such expenses on behalf of such sellers.

“Securities Act” means the Securities Act of 1933, as amended, or any similar federal statute, and the rules and regulations of the Commission promulgated thereunder, all as the same shall be in effect from time to time.

“Series A Preferred” means the Series A Convertible Preferred Stock, par value $0.001 per share, of the Company.

“Series B-1 Preferred” means the Series B-1 Convertible Preferred Stock, par value $0.001 per share, of the Company.

“Series B-2 Preferred” means the Series B-2 Convertible Preferred Stock, par value $0.001 per share, of the Company.

- 11 -

“Series C Preferred” means the Series C Convertible Preferred Stock, par value $0.001 per share, of the Company that may be issued after the date hereof.

Section 13. Miscellaneous.

(a) No Inconsistent Agreements. The Company will not without the consent of Investors holding at least two-thirds of the outstanding shares of Preferred Stock (or Common Stock issued upon conversion of the Preferred Stock) hereafter enter into any agreement with respect to its securities which is inconsistent with or violates the rights granted to the Stockholders in this Agreement or which grants to any other person or entity rights as to registration which are superior to or more beneficial than the rights granted hereunder.

(b) Adjustments Affecting Registrable Securities. The Company will not take any action, or permit any change to occur, with respect to its securities that would adversely affect the ability of the Stockholders to include their Registrable Securities in a registration undertaken pursuant to this Agreement or which would adversely affect the marketability of such Registrable Securities in any such registration.

(c) Specific Performance; Other Rights. The parties recognize that various of the rights of the Stockholders under this Agreement are unique and, accordingly, the Stockholders shall, in addition to such other remedies as may be available to any of them at law or in equity, have the right to enforce their rights hereunder by actions for injunctive relief and specific performance to the extent permitted by law. The Company hereby waives any requirement for security or the posting of any bond in connection with any temporary or permanent award of injunctive, mandatory or other equitable relief.

(d) Successors and Assigns. Except as otherwise set forth herein, all covenants, agreements and representations made herein shall bind and inure to the benefit of each party hereto, and their respective successors and assigns.

(e) Notices and Communications. Any and all notices, consents, approvals, offers, elections and other communications required or permitted under this Agreement shall be deemed adequately given only if in writing and the same shall be delivered either by hand, by facsimile or by expedited commercial carrier, addressed to the recipient of the notice, charges prepaid. All communications to be sent hereunder shall be deemed to have been given for all purposes of this Agreement upon the date of receipt or refusal. All such notices shall be addressed as follows:

- 12 -

If to a Stockholder: to such Stockholder’s address as set forth on Schedule 1 or 2 hereto

or at such other address or addresses as may have been furnished in writing by any party to the others.

Notices and other communications provided in accordance herewith shall be deemed delivered on (i) the date on which personally delivered, with receipt acknowledged, (ii) the date on which sent by facsimile with confirmation, (iii) the next business day if delivered by domestic overnight or express mail, courier or delivery service, or (iv) the third business day after the same shall have been sent by international overnight or express mail, courier or delivery service, as the case may be. Failure or delay in delivering copies of any notice, demand, request, consent, approval, declaration or other communication to the persons designated above to receive copies shall in no way adversely affect the effectiveness of such notice, demand, request, consent, approval, declaration or other communication.

(f) Amendments and Waivers. This Agreement may only be amended with the consent of the Company and Investors holding at least a two-thirds of the Registrable Securities held by all Investors. Except as otherwise expressly set forth in this Agreement, the observance of any term of this Agreement may be waived (either generally or in a particular instance and either retroactively or prospectively), only with the written consent of the Company and Investors holding at least two-thirds of the Registrable Securities held by all Investors. No waivers of or exceptions to any term, condition or provision of this Agreement, in any one or more instances, shall be deemed to be, or construed as, a further or continuing waiver of any such term, condition or provision. Notwithstanding the foregoing, any amendment or waiver that (i) treats any Investor in a materially adverse manner that is different from any other Investor, (ii) treats any Common Holder in a materially adverse manner that is different from any other Common Holder, or (iii) that eliminates or materially adversely modifies any rights of any Common Holder, will require the separate approval of such Investor or Common Holder. Any amendment or waiver in accordance herewith shall be binding upon each party hereto.

(g) Headings; Counterparts. Headings in this Agreement are for purposes of reference only and shall not limit or otherwise affect the meaning hereof. This Agreement may be executed in any number of counterparts, each of which shall be an original, but all of which together shall constitute one instrument.

(h) Number; Gender. Whenever used herein the singular number shall include the plural, the plural shall include the singular, and the use of any gender shall include all genders.

(i) Further Assurances. Each of the parties hereto agrees to execute and deliver those writings and documents reasonably required to more fully carry out the purposes of this Agreement and the transactions contemplated hereby.

(j) Governing Law. This Agreement shall be construed in accordance with and governed by the law (other than the law governing conflict of law questions) of the State of Delaware.

(k) Severability. If any provision of this Agreement shall be held or deemed to be, or shall in fact be, invalid, inoperative or unenforceable as applied to any particular case in any jurisdiction or jurisdictions, or in all jurisdictions or in all cases, because of the conflicting of any provision with any constitution or statute or rule of public policy or for any other reason, such circumstance shall not have the effect of rendering the provision or provisions in question, invalid, inoperative or unenforceable in any other jurisdiction or in any other case or circumstance or of rendering any other provision or provisions herein contained invalid, inoperative or unenforceable to the extent that such other provisions are not themselves actually in conflict with such constitution, statute or rule of public policy, but this

- 13 -

Agreement shall be reformed and construed in any such jurisdiction or case as if such invalid, inoperative or unenforceable provision had never been contained herein and such provision reformed so that it would be valid, operative and enforceable to the maximum extent permitted in such jurisdiction or in such case.

(l) Aggregation of Stock. All shares of Registrable Securities held or acquired by Affiliates shall be aggregated together for the purpose of determining the availability of any rights under this Agreement.

(m) Entire Agreement. The parties hereto agree that this Agreement constitutes the entire agreement among the parties with respect to the subject matter hereof and supersedes all prior agreements and understandings between them as to such subject matter including the First Amended and Restated Agreement, which is superseded by this Agreement and is of no further force and effect; and there are no restrictions, agreements, arrangements, oral or written, between any or all of the parties relating to the subject matter hereof which are not fully expressed or referred to herein.

(n) New Stockholders. Except as specifically provided herein, any individual or Entity that, after the date hereof, acquires shares of Stock must as a condition to the effectiveness of such acquisition become a party to this Agreement, unless such requirement is waived by the action of a majority of the Board of Directors (including the approval of at least one of the Preferred Stock Directors as defined in the Stockholders’ Agreement). Each such individual or Entity shall become a party to this Agreement, without the need for the consent, approval or signature of any other Stockholder, by executing a joinder or other instrument acceptable to and executed by the Company; thereafter, such individual or Entity shall become a “Stockholder” hereunder (and a “Investor” with respect to individuals and Entities acquiring shares of Preferred Stock).

(o) Arbitration. Except as otherwise specifically provided herein, all disputes, controversies, claims or differences that may arise among the parties hereto out of or in relation to this Agreement (including questions as to whether a matter is governed by this arbitration provision) shall be settled solely and exclusively by arbitration (if good faith negotiations among the parties do not resolve such dispute, controversy, claim or difference within sixty (60) days after notice of such dispute is received) conducted in accordance with the Commercial Arbitration Rules of the American Arbitration Association. All hearings and proceedings regarding arbitration shall take place in Santa Clara County, Chicago, before a single arbitrator acceptable to both parties. The arbitrator shall be chosen from a panel of approved arbitrators of the American Arbitration Association. Reasonable discovery shall be allowed. The arbitrator shall abide by the clear and unambiguous terms of this Agreement in making a determination. The costs and fees of the arbitration, including reasonable attorneys’ fees of the parties, shall be allocated by the arbitrator taking into account the parties’ intent and agreement that the prevailing party in such dispute shall be entitled to an award of costs and expenses. The award rendered by the arbitrator shall be final and binding upon the parties. Judgment on the award may be entered in accordance with applicable law in any court having jurisdiction thereof. Nothing herein shall bar any party from obtaining injunctive relief as provided for in this Agreement or against other threatened conduct under rules of equity.

(p) Expenses. If any action at law or in equity is necessary to enforce or interpret the terms of this Agreement, the prevailing party shall be entitled to reasonable attorneys’ fees, costs and necessary disbursements in addition to any other relief to which such party may be entitled.

[remainder of page intentionally left blank]

- 14 -

IN WITNESS WHEREOF, the parties have caused this Agreement to be executed under seal by their respective duly authorized officers as of the day and year first above written.

[Signature Page to Neutral Tandem, Inc. Second Amended and

Restated Registration Rights Agreement]

[Signature Page to Neutral Tandem, Inc. Second Amended and

Restated Registration Rights Agreement]

[Signature Page to Neutral Tandem, Inc. Second Amended and

Restated Registration Rights Agreement]

[Signature Page to Neutral Tandem, Inc. Second Amended and

Restated Registration Rights Agreement]