Exhibit 23.1

Report and Consent of Independent Registered Public Accounting Firm

The Board of Directors and Stockholders

Lumos Networks Corp.:

The audits referred to in our report dated March 8, 2013, with respect to the consolidated financial statements of Lumos Networks Corp. (the Company), included the related financial statement schedule (Schedule II - Valuation and Qualifying Accounts) as of December 31, 2012 and 2011 and for each of the years in the three-year period ended December 31, 2012 included in Item 15(a)2 of the Company’s 2012 Annual Report on Form 10-K. This financial statement schedule is the responsibility of the Company’s management. Our responsibility is to express an opinion on this financial statement schedule based on our audits. In our opinion, such financial statement schedule, when considered in relation to the basic consolidated financial statements taken as a whole, presents fairly in all material respects the information set forth therein.

We consent to the incorporation by reference in the Registration Statement No. 333-177627 on Form S-8 of the Company of our reports dated March 8, 2013, with respect to the consolidated balance sheets of the Company as of December 31, 2012 and 2011, and the related consolidated statements of operations, comprehensive income (loss), cash flows, and equity for each of the years in the three-year period ended December 31, 2012, and the related financial statement schedule, and the effectiveness of internal control over financial reporting as of December 31, 2012, which reports appear in the 2012 Annual Report on Form 10-K of the Company.

/s/ KPMG LLP

Richmond, Virginia

March 8, 2013