EXHIBIT 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

To the Plan Administrator of the

First Federal Bancshares of Arkansas, Inc.

   Employees’ Savings & Profit Sharing Plan

Harrison, Arkansas

We consent to the incorporation by reference in Registration Statement No. 333-135402 on Form S-8 of First Federal Bancshares of Arkansas, Inc. of our report dated June 26, 2013, with respect to the financial statements and supplemental schedule of the First Federal Bancshares of Arkansas, Inc. Employees’ Savings & Profit Sharing Plan as of and for the years ended December 31, 2012 and 2011, which are included in this annual report on Form 11-K.

/s/ Frost, PLLC

Little Rock, Arkansas

June 26, 2013