Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We have issued our reports dated March 14, 2016, with respect to the consolidated financial statements and internal control over financial reporting included in the Annual Report of Sterling Construction Company, Inc. on Form 10-K for the year ended December 31, 2015. We consent to the incorporation by reference of said reports in the Registration Statements of Sterling Construction Company, Inc. on Form S-3 (File No. 333-195087, effective April 29, 2014) and Forms S-8 (File No. 333-204085, effective May 12, 2015, File No. 333-196457, effective June 2, 2014, File No. 333-88228, effective May 14, 2002 and File No. 333-135666, effective July 10, 2006).

/s/ GRANT THORNTON LLP

Houston, Texas

March 14, 2016