Exhibit 32

The undersigned, as the chief executive officer and chief financial officer of MainStreet BankShares, Inc., certify that to the best of our knowledge and belief the Form 10-Q for the quarter ended September 30, 2009, fully complies with the requirements of Section 13(a) or 15(d), as applicable, of the Securities Exchange Act of 1934 and the information contained in the periodic report fairly presents, in all material respects, the financial condition and results of operations of MainStreet BankShares, Inc. at the dates and for the periods indicated. The foregoing certification is made solely for purposes of 18 USC, Section 1350 of the United States Code and is subject to the knowledge and willfulness qualifications contained in Title 18, Chapter 63, Section 1350(c).

49