Exhibit 23

Consent of Independent Registered Public Accounting Firm

The Plan Administrator

Fastenal Company & Subsidiaries 401(k) and Employee Stock Ownership Plan:

We consent to the incorporation by reference in the registration statements (Nos. 333-52765 and 333-176401) on Form S-8 of Fastenal Company of our report dated June 22, 2016 with respect to the statements of net assets available for benefits of the Fastenal Company & Subsidiaries 401(k) and Employee Stock Ownership Plan as of December 31, 2015 and 2014, the related statement of changes in net assets available for benefits for the year ended December 31, 2015, and the supplemental Schedule H, Line 4i – Schedule of Assets (Held at End of Year) as of December 31, 2015, which report appears in the December 31, 2015 annual report on Form 11-K of the Fastenal Company & Subsidiaries 401(k) and Employee Stock Ownership Plan.

/s/ KPMG LLP

Minneapolis, Minnesota

June 22, 2016