SECURITIES AND EXCHANGE COMMISSION
                              WASHINGTON, DC 20552
                           --------------------------

                                    FORM 10-Q
(Mark One)


[|X|]    QUARTERLY REPORT PURSUANT TO SECTION 13 OR 15(d) OF THE SECURITIES
         EXCHANGE ACT OF 1934 For the quarterly period ended March 31, 2004
                                       OR

[  ]     TRANSITION REPORT PURSUANT TO SECTION 13 OR 15(d) OF THE SECURITIES
         EXCHANGE ACT OF 1934

         For the transition period from  _________________to___________________

         Commission File Number   0-29040 ____________________________________
                                  --------
                            Fidelity Bankshares, Inc.
- -------------------------------------------------------------------------------
             (Exact name of registrant as specified in its charter)

        Delaware                                           65-0717085
- -------------------------------             -----------------------------------
(State or other jurisdiction of             (I.R.S. Employer Identification No.)
incorporation or organization)

205 Datura Street, West Palm Beach, Florida                         33401
- --------------------------------------------------------------------------------
(Address of principal executive offices)                           (Zip Code.)

                                 (561) 803-9900
- -------------------------------------------------------------------------------
              (Registrant's telephone number, including area code)

(Former name,former address and former fiscal year,if changed since last report)

     Indicate  by check  mark  whether  the  Registrant  has filed  all  reports
required to be filed by Sections 13, or 15(d) of the Securities  Exchange Act of
1934  during  the  preceding  12 months  (or for such  shorter  period  that the
Registrant was required to file such reports),  and (2) has been subject to such
filing  requirements  for the past 90 days.  Yes |X| No  Indicate  by check mark
whether the Registrant is an accelerated  filer (as defined in Rule 12b-2 of the
Exchange Act). Yes |X| No

                APPLICABLE ONLY TO ISSUERS INVOLVED IN BANKRUPTCY
                   PROCEEDING DURING THE PRECEDING FIVE YEARS:

     Indicate by check mark whether the  Registrant  has filed all documents and
reports  required  to be filed by  Sections  12, 13, or 15(d) of the  Securities
Exchange Act of 1934 subsequent to the  distribution of securities  under a plan
confirmed by a court. Yes |X| No

SEC 1296  (1-04)  Potential  persons  who are to  respond to the  collection  of
                  information contained in this form are not required to respond
                  unless the form displays a currently valid OMB control number.

<page>


                            FIDELITY BANKSHARES, INC.
                                      INDEX

                                                                            Page
PART I.       FINANCIAL INFORMATION

Item 1. Financial Statements..................................................1

        Unaudited Condensed Consolidated Statements of Financial Condition as of
           December 31, 2003 and March 31, 2004................................2

         Unaudited Condensed Consolidated Statements of Operations for the three
           months ended March 31, 2003 and 2004................................3

         Unaudited Condensed Consolidated Statements of Comprehensive Operations
           for the three months ended March 31, 2003 and 2004..................4

         Unaudited Condensed Consolidated Statements of Cash Flows for the three
            months ended March 31, 2003 and 2004...............................5

         Notes to Unaudited Condensed Consolidated Financial Statements........6

Item 2.  Management's Discussion and Analysis of Financial Condition
            and Results of Operations.........................................13

Item 3.  Quantitative and Qualitative Disclosure About Market Risk............17

Item 4.  Controls and Procedures..............................................23

PART II. OTHER INFORMATION....................................................24

 Item 1. Legal Proceedings....................................................24

 Item 2. Changes in Securities................................................25

 Item 3. Default Upon Senior Securities.......................................25

 Item 4. Submissions of matters to a Vote of Security.........................25

 Item 5. Other Information....................................................25

 Item 6. Exhibits and Reports on Form 8-K.....................................25

EXHIBITS

         Section 302 Certification

         Section 906 Certification





PART I.  FINANCIAL INFORMATION

Item I.  Financial Statements

FIDELITY BANKSHARES, INC.
UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF FINANCIAL CONDITION
- --------------------------------------------------------------------------------



                                                                                               December 31,        March 31,
                                                                                                   2003              2004
                                                                                          ========================================
ASSETS                                                                                   (In thousands, except share and per share
                                                                                            data)
CASH AND CASH EQUIVALENTS:
                                                                                                             
     Cash and amounts due from depository institutions........................                $    76,090          $   109,739
     Interest-earning deposits................................................                     33,797              192,170
                                                                                              -----------          -----------
         Total cash and cash equivalents......................................                    109,887              301,909
                                                                                              -----------          -----------
ASSETS AVAILABLE FOR SALE (At Fair Value):
     Municipal bonds and government and agency securities.....................                    122,731              143,293
     Mortgage-backed securities...............................................                    471,228              360,961
                                                                                              -----------          ------------
         Total assets available for sale......................................                    593,959              504,254
LOANS RECEIVABLE, Net.........................................................                  2,191,696            2,280,624
OFFICE PROPERTIES AND EQUIPMENT, Net..........................................                     73,553               75,083
FEDERAL HOME LOAN BANK STOCK, At cost, which approximates market..............                     13,322               13,055
REAL ESTATE OWNED AND OTHER REPOSSESSED ASSETS................................                         -                    17
ACCRUED INTEREST RECEIVABLE...................................................                     11,127               11,001
DEFERRED INCOME TAX ASSET.....................................................                      7,598                5,561
OTHER ASSETS                                                                                       47,080               49,282
                                                                                              -----------          -----------
TOTAL ASSETS                                                                                  $ 3,048,222          $ 3,240,786
                                                                                              ===========          ===========

LIABILITIES AND STOCKHOLDERS' EQUITY
LIABILITIES
DEPOSITS .....................................................................                $ 2,460,101          $ 2,641,322
OTHER BORROWED FUNDS..........................................................                     42,089               38,829
ADVANCES FROM FEDERAL HOME LOAN BANK..........................................                    264,561              261,107
ADVANCES BY BORROWERS FOR TAXES AND INSURANCE.................................                      2,816                9.351
DRAFTS PAYABLE................................................................                        202                  807
GUARANTEED PREFERRED BENEFICIAL INTERESTS IN COMPANY'S
     JUNIOR SUBORDINATED DEBENTURES...........................................                     52,320               52,320
OTHER LIABILITIES.............................................................                     41,624               44,366
                                                                                              -----------          -----------
     TOTAL LIABILITIES........................................................                  2,863,713            3,048,102
                                                                                              -----------          -----------

STOCKHOLDERS' EQUITY:
PREFERRED STOCK, 2,000,000 shares authorized, none issued.....................                          -                    -
COMMON STOCK ($.10 par value) 30,000,000 authorized shares:
     15,024,648 shares issued at December 31, 2003 and 15,070,258 shares issued at                  1,502                1,507
March 31, 2004................................................................
ADDITIONAL PAID IN CAPITAL....................................................                    106,392              105,369
RETAINED EARNINGS - substantially restricted..................................                     89,793               95,755
TREASURY STOCK - at cost, 314,694 shares at December 31, 2003 and
     297,706 shares at March 31, 2004.........................................                     (1,794)              (1,741)
COMMON STOCK ALLOCATED TO:
     Employee stock ownership plan............................................                     (4,257)              (4,169)
     Recognition and retention plan...........................................                     (4,410)              (4,032)
ACCUMULATED OTHER COMPREHENSIVE LOSS..........................................                     (2,717)                  (5)
                                                                                              ------------         ------------
     TOTAL STOCKHOLDERS' EQUITY...............................................                     184,509              192,684
                                                                                              ------------         ------------

TOTAL LIABILITIES AND STOCKHOLDERS' EQUITY....................................                $  3,048,222       $    3,240,786
                                                                                              =============      ==============


See Notes to Unaudited Condensed Consolidated Financial Statements.

                                       1



FIDELITY BANKSHARES, INC.
- --------------------------------------------------------------------------------
UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS



                                                                                                 For the
                                                                                           Three Months Ended
                                                                                                March 31,
                                                                                           2003              2004
                                                                                  ====================================
                                                                                  (In Thousands, except per share data)
Interest income:
                                                                                                     
     Loans.............................................................              $   31,881            32,759
     Investment securities.............................................                     397               568
     Other investments.................................................                     524               286
     Mortgage-backed and corporate debt securities.....................                   2,029             4,449
                                                                                        -------            ------
         Total interest income.........................................                  34,831            38,062
                                                                                        -------            ------
Interest expense:
     Deposits..........................................................                   9,428             9,373
     Advances from Federal Home Loan Bank and other borrowings.........                   4,618             4,776
                                                                                        -------             -----
         Total interest expense........................................                  14,046            14,149
                                                                                        -------            ------

Net interest income....................................................                  20,785           23,913

Provision for loan losses..............................................                     790              596
                                                                                        -------           ------

Net interest income after provision for loan losses....................                  19,995           23,317
                                                                                        -------           ------
Other income:
     Service charges on deposit accounts...............................                   1,902            2,839
     Fees for other banking services...................................                   2,294            2,672
     Net gain on sale of loans.........................................                   2,559              105
     Net gain on sale of Investments...................................                       -              587
     Miscellaneous.....................................................                     256              260
                                                                                        -------           ------
         Total other income............................................                   7,011            6,463
                                                                                        -------           ------
Operating expense:
     Employee compensation and benefits................................                  11,096           11,944
     Occupancy and equipment...........................................                   3,416            4,010
     (Gain)/loss on real estate owned and other repossessed assets.....                      63               (8)
     Marketing.........................................................                     497              589
     Federal deposit insurance premium.................................                      77               90
     Miscellaneous.....................................................                   3,511            3,841
                                                                                        -------           ------
         Total operating expense.......................................                  18,660           20,466
                                                                                        -------           ------

Income before provision for income taxes...............................                   8,346            9,314
                                                                                        -------           ------
Provision for income taxes:
     Current...........................................................                   2,960            3,324
     Deferred..........................................................                     269              303
                                                                                        -------           ------
         Total provision for income taxes..............................                   3,229            3,627
                                                                                        -------           ------

              Net income...............................................                $  5,117          $ 5,687
                                                                                        =======           ======

Earnings per share:
     Basic.............................................................                $   0.36          $  0.39
                                                                                       =======           =======
     Diluted...........................................................                $   0.35          $  0.38
                                                                                       =======           =======


See Notes to Unaudited Condensed Consolidated Financial Statements.

                                       2



FIDELITY BANKSHARES, INC.
UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF COMPREHENSIVE OPERATIONS
- --------------------------------------------------------------------------------



                                                                                  For the
                                                                             Three Months Ended
                                                                                  March 31,
                                                                             2003             2004
                                                                      ===============================
                                                                               (In Thousands)


                                                                                       
Net Income..............................................................    $ 5,117       $  5,687
Other comprehensive income (loss), net of tax:
     Unrealized gains (losses) on assets available for sale:
         Unrealized holding gains (losses) arising during period........       (651)         2,712
                                                                              ------      --------

Comprehensive income................................................ ...    $ 4,466       $  8,399
                                                                             =======       =======



See Notes to Unaudited Condensed Consolidated Financial Statements.

                                       3

<page>

FIDELITY BANKSHARES, INC.
- --------------------------------------------------------------------------------
UNAUDITED CONDENSED CONSOLIDATED STATEMENTS OF CASH FLOWS



                                                                                  For the Three Months Ended
                                                                                           March 31,
                                                                                      2003              2004
                                                                                  ==========================
                                                                                              (In Thousands)
CASH FLOWS FROM (FOR) OPERATING ACTIVITIES:
                                                                                               
Net Income.............................................................            $  5,117          $  5,687
Adjustments to reconcile net income to net cash provided by operating
activities:
   Depreciation........................................................                 985             1,430
   ESOP and recognition and retention plan compensation expense........                 599               697
   Accretion of discounts, amortization of premiums and goodwill, and                  (638)             (475)
    other deferred yield items.........................................
   Provision for loan losses...........................................                 790               596
   Provisions for losses and net (gains) losses on sales of real estate
         owned and other repossessed assets............................                   -                (8)
   Net (gain) loss on sale of:
         Loans.........................................................              (2,559)             (105)

         Mortgage-backed securities....................................                   -              (587)
         Office properties and equipment...............................                   -                 7
   Decrease (increase) in accrued interest receivable..................                (688)              126
   Increase in other assets............................................              (4,106)           (2,229)
   Decrease in drafts payable..........................................               4,182               605
   Decrease in deferred income taxes...................................                (147)              303
   Increase in other liabilities.......................................               7,774             2,750
                                                                                   --------          --------
         Net cash provided by operating activities.....................              11,309             8,797
                                                                                   --------          --------
CASH FLOW FROM (FOR) INVESTING ACTIVITIES:
Loan originations and principal payments on loans......................             (91,387)          (88,243)
Principal payments received on mortgage-backed securities..............              29,902            47,626
Purchases of:
   Loans...............................................................             (12,231)           (8,523)
   Mortgage-backed securities..........................................            (270,201)          (48,581)
   Federal Home Loan Bank stock........................................                (955)           (2,511)
   Investment securities...............................................             (40,000)          (20,162)
   Office properties and equipment.....................................              (1,751)           (2,983)
Proceeds from sales of:
   Loans...............................................................              86,431             8,329

   Federal Home Loan Bank stock........................................                   -             2,778
   Real estate and other assets acquired in settlement of loans........                   -                35


   Mortgage-backed securities available for sale.......................                   -           115,394
Proceeds from maturities of municipal bonds and government and agency                79,000                 -
securities
Other..................................................................                 252               436
                                                                                   --------          --------
         Net cash used for investing activities........................            (220,940)            3,595
                                                                                   --------          --------
CASH FLOW FROM (FOR) FINANCING ACTIVITIES:
Proceeds from the sale of common stock and exercise of stock options,                   108                45
net of issuance costs..................................................
Purchase of treasury stock.............................................                 (10)                -
Cash dividends paid....................................................              (1,437)           (1,457)
Net increase (decrease) in:
   NOW accounts, demand deposits and savings accounts..................             240,152           189,651
   Certificates of deposit.............................................             (10,419)           (8,430)
   Advances from Federal Home Loan Bank................................              21,595            (3,454)
   Other borrowed funds................................................             (10,307)           (3,260)
   Advances by borrowers for taxes and insurance.......................               3,413             6,535
                                                                                   --------          --------
         Net cash provided by financing activities.....................             243,095           179,630
                                                                                   --------          --------
NET INCREASE IN CASH AND CASH EQUIVALENTS..............................              33,464           192,022
CASH AND CASH EQUIVALENTS, Beginning of period.........................             129,666           109,887
                                                                                   --------          --------
CASH AND CASH EQUIVALENTS, End of period...............................            $163,130          $301,909
                                                                                   ========          ========

See Notes to Unaudited Condensed Consolidated Financial Statements.
                                       4
<page>

NOTES TO UNAUDITED CONDENSED CONSOLIDATED FINANCIAL STATEMENTS
- --------------------------------------------------------------------------------

1.   GENERAL

The  accounting  and  reporting  policies  of  Fidelity  Bankshares,  Inc.  (the
"Company") and its subsidiary Fidelity Federal Bank & Trust (the "Bank") conform
to accounting  principles generally accepted in the United States of America and
to predominant practices within the thrift industry. The Company has not changed
its  accounting and reporting  policies from those  disclosed in its 2003 Annual
Report on Form 10-K.

In December  2002,  the FASB issued SFAS No. 148,  "Accounting  for  Stock-Based
Compensation-Transition  and Disclosure, an amendment of FASB Statement No. 123"
to provide  alternative methods of transition for a voluntary change to the fair
value based method of  accounting  for  stock-based  employee  compensation.  In
addition,  this statement amends the disclosure requirements of Statement 123 to
require prominent  disclosures in both annual and interim  financial  statements
about the method of accounting for  stock-based  employee  compensation  and the
effect of the method used on reported  results.  The provisions of Statement 148
are effective for interim periods  beginning after December 15, 2002, with early
application  encouraged.  The adoption of the disclosure  provisions of SFAS No.
148 did not have a material  effect on the  Company's  results of  operations or
financial  position.  The  disclosures  pursuant to SFAS No. 148 may be found in
Note 2.

In January 2003,  the FASB issued FIN 46,  "Consolidation  of Variable  Interest
Entities" which addresses  consolidation of variable  interest entities ("VIEs")
certain of which are also referred to as special purpose entities ("SPEs").  The
FASB  revised  FIN 46 in  December  2003.  VIEs are  entities  in  which  equity
investors do not have the characteristics of a controlling financial interest or
do not have  sufficient  equity at risk for the entity to finance its activities
without additional  subordinated financial support from other parties. Under the
provisions  of FIN 46, a company is to  consolidate  a VIE if the  company has a
variable  interest (or  combination  of variable  interests)  that will absorb a
majority of the VIE's expected  losses if they occur,  receive a majority of the
VIE's expected  residual returns if they occur, or both. The  implementation  of
FIN 46 is required for public  entities at the end of the first  interim  period
ending after March 15, 2004 if the VIE was created before February 1, 2003, with
early adoption  allowed,  and immediately for entities created after February 1,
2003.  The Company  early  adopted FIN 46 and has  deconsolidated  the  Fidelity
Capital Trust I at December 31, 2003. The  deconsolidation  of Fidelity  Capital
Trust I did not have a material impact on the Company's  consolidated  financial
position or results of operations.

On May 15, 2003, the FASB issued SFAS No. 150, "Accounting for Certain Financial
Instruments with  Characteristics  of Both Liabilities and Equity." SFAS No. 150
was effective May 31, 2003 for all new and modified  financial  instruments  and
otherwise effective at the beginning of the first interim period beginning after
June 15,  2003.  SFAS No. 150  changes  the  accounting  for  certain  financial
instruments  that,  under previous  guidance,  could be accounted for as equity.
SFAS No. 150 requires that those  instruments be classified as liabilities or in
some circumstances  assets. In November 2003, the FASB indefinitely deferred the
effective  date for the  classification  and  measurement  provisions of certain
mandatorily redeemable noncontrolling interests under SFAS No. 150. The adoption
of this  statement did not have a material  impact on the  Company's  results of
operations or financial conditions.

In November 2003,  the EITF reached a consensus on the disclosure  provisions of
EITF Issue No. 03-1,  "The Meaning of  Other-Than-Temporary  Impairment  and its
Application  to  Certain  Investments."  EITF No.  03-1  requires  that  certain
quantitative  and  qualitative  disclosures be made for certain debt  securities
classified as  available-for-sale  under SFAS No. 115,  "Accounting  for Certain
Investments  in Debt and Equity  Securities,"  that are  impaired at the balance
sheet  date  but for  which  an  other-than-temporary  impairment  has not  been
recognized.  Debt securities  within the scope of EITF Issue No. 99-20,  are not
                                       5
<page>

subject to these disclosure provisions.  The disclosures are required for fiscal
years ending after  December 15, 2003, and  accordingly  the Company has adopted
the disclosure provisions of EITF No. 03-1 for the year ended December 31, 2003.

In December 2003, the FASB Issued  Statement of Financial  Accounting  Standards
No.  132  (revised  2003),  "Employees  Disclosures  about  Pensions  and  Other
Postretirement Benefits," an amendment of FASB Statements No. 87, 88 and 106, to
address  the  increasing  significance  of  corporate  pension  plans to company
financial statements and the call for greater transparency in financial reports.
The statement requires additional disclosures, regarding plan assets, investment
strategy,  measurement date, plan obligations,  cash flows and components of net
periodic benefit cost of defined benefit pension plans and other  postretirement
benefit  plans.  However,  it does not change the  measurement or recognition of
those plans  required by SFAS No. 87, SFAS No. 88 and SFAS No. 106.  The Company
has  adopted  the  disclosure  provisions  of EITF No.  03-1 for the year  ended
December 31, 2003.

Certain amounts in the financial  statements  have been  reclassified to conform
with the March 31, 2004 presentation.

                                       6


2.   STOCK OPTION PLANS

At March 31, 2004, the Company has three  stock-based  compensation  plans.  The
Company accounts for these plans using the intrinsic value method  prescribed by
APB Opinion  No. 25  "Accounting  for Stock  Issued to  Employees",  and related
interpretations.  Accordingly,  no stock option-based employee compensation cost
is  reflected  in net income,  as all options  granted  under those plans had an
exercise price equal to the market value of the  underlying  common stock on the
date of grant.  The  following  table  illustrates  the effect on net income and
earnings  per  share if the  Company  had  applied  the fair  value  recognition
provisions  of SFAS No.  123,  "Accounting  for  Stock-Based  Compensation",  to
stock-based employee compensation.




                                                                                    For the
                                                                                Three Months Ended
                                                                                    March 31,
                                                                              2003             2004
                                                                          ============================
                                                                                  (In Thousands)
                                                                                        
Net Income, as reported...................................................  $   5,117       $  5,687
    Add: Total stock-based employee compensation expense included
      in reported net earnings, net of related tax effects................        259            230
    Deduct: Total stock-based employee compensation
      expense determined under fair value based method
      for all awards, net of related tax effects..........................       (384)          (479)
                                                                               -------       --------

Pro forma net income......................................................  $   4,992       $  5,438
                                                                             ==========     =========

    Basic - as reported................................................          0.36           0.39
    Basic - pro forma..................................................          0.35           0.37

    Diluted - as reported..............................................          0.35           0.38
    Diluted - pro forma................................................          0.34           0.36



3.   LOANS RECEIVABLE

Loans  receivable  at  December  31,  2003 and March 31,  2004,  consist  of the
following:



                                                                              December 31,       March 31,
                                                                                2003               2004
                                                                            ==============   ==============
                                                                                        (In Thousands)

                                                                                          
One-to-four single family, residential real estate mortgages.........         $1,002,573        $1,016,989
Commercial and multi-family real estate mortgages....................            753,890           785,814
Real estate construction-primarily residential.......................            470,016           483,703
Land loans-primarily residential.....................................             36,660            44,396
                                                                              ----------        ----------
Total first mortgage loans...........................................          2,263,139         2,330,902
Consumer loans.......................................................            185,450           190,984
Commercial business loans............................................            131,292           133,174
                                                                              ----------        ----------
Total gross loans....................................................          2,579,881         2,655,060
Add/(deduct):
     Undisbursed portion of loans in process.........................           (374,974)         (360,507)
     Unearned discounts, premiums and deferred loan fees (costs), net              2,092            (2,277)
     Allowance for loan losses.......................................            (11,119)          (11,652)
                                                                              -----------       -----------
Loans receivable-net.................................................         $2,191,696         $2,280,624
                                                                              ==========         ==========

                                     7
<page>

During the quarter ended March 31, 2004, the Company sold $8.2 million in loans,
which resulted in net gains of approximately $105,000. The Company has initiated
a loan sales program to provide additional non interest income,  reduce interest
rate risk and as a capital  management tool. At March 31, 2004, the Company held
$1.2 million in loans available for sale.

4.   ALLOWANCE FOR LOAN LOSSES

An analysis of the changes in the  allowance  for loan losses for the year ended
December 31, 2003 and the three month  periods ended March 31, 2003 and 2004, is
as follows:




                                            For the Year               For the Three Months
                                               Ended                          Ended
                                            December 31,                    March 31,
                                                2003                    2003           2004
                                         ====================      ==========================
                                           (In Thousands)                (In Thousands)

                                                                             
Balance at beginning of period......        $      8,318              $ 8,318         $ 11,119

Current provision...................               3,122                  790              596

Charge-offs.........................                (322                  (72)             (67)
Recoveries..........................                   1                    -                4
                                            ------------             -----------    -----------

Ending balance......................        $     11,119              $ 9,036        $  11,652
                                            ============             ===========    ===========



An analysis of the recorded investment in impaired loans owned by the Company at
the end of each period and the related  specific  valuation  allowance for those
loans is as follows:



                                                                    December 31, 2003             March 31, 2004
                                                                =====================================================

                                                                    Loan        Related         Loan         Related
                                                                  Balance      Allowance       Balance      Allowance
                                                                ------------- ------------- -------------- -------------
                                                                                    (In Thousands)
Impaired loan balances and related allowances:
                                                                                                
Loans with related allowance for loan losses................     $  3,508      $    598      $  3,398       $    538
Loans without related allowance for loan losses.............        9,162             -         9,295              -
                                                                 --------      --------      --------       --------
         Total..............................................     $ 12,670      $    598      $ 12,693       $    538
                                                                 ========      ========      ========       ========


The Bank's  policy  for  interest  income on  impaired  loans is to reverse  all
accrued  interest  against  interest  income if a loan becomes more than 90 days
delinquent  and cease accruing  interest  thereafter.  Such interest  ultimately
collected is credited to income in the period of recovery.
                                       8



5.   DEPOSITS

The  weighted-average  interest rates on deposits at December 31, 2003 and March
31,  2004 were  1.51% and  1.49%,  respectively.  Deposit  accounts,  by type at
December 31, 2003 and March 31, 2004 consist of the following:



                                                                  December 31,     March 31,
                        Account Type and Rate                         2003           2004
                                                                  ========= ==============
                                                                        (In Thousands)

                                                                          
Non-interest-bearing checking accounts.....................       $  294,358      $339,255
Interest-bearing checking and funds transfer accounts......          566,028       612,861
Passbook and statement accounts............................          615,972       666,019
Variable-rate money market accounts........................          297,864       345,738
Certificates of deposit....................................          685,879       677,449
                                                                  ----------    ----------

Total......................................................       $2,460,101    $2,641,322
                                                                  ==========    ==========


6.   REGULATORY CAPITAL

The  Company's  subsidiary,  Fidelity  Federal  Bank  &  Trust,  is a  regulated
financial  institution.  Its regulatory capital amounts and ratios are presented
in the following table:


                                                                                                     To be Considered
                                                                           Minimum for               Well Capitalized
                                                                        Capital Adequacy           for Prompt Corrective
                                                   Actual                   Purposes                 Action Provisions
                                        -- ---------- ------------ -------------- ------------- ------------- --------------
                                             Ratio      Amount         Ratio         Amount        Ratio         Amount
                                        -- ---------- ------------ -------------- ------------- ------------- --------------
                                                                        (Dollars in Thousands)
As of December 31, 2003 Stockholders'
                                                                                             
     Equity and ratio to total assets          7.2%     $  220,528
                                          ========
Unrealized decrease in market value
     of assets available for sale
     (net of applicable income taxes)                        1,060
Goodwill.............................                       (5,615)
Disallowed servicing assets..........                         (124)
                                                        ---------
Tangible capital and ratio to
     adjusted total assets...........          7.1%     $  215,849       1.5%       $  45,630
                                          ========      ==========    ======        =========
Tier I (core) capital and ratio to
     adjusted total assets...........          7.1%     $  215,849       3.0%       $  91,259        5.0%       $ 152,099
                                          ========      ==========    ======        =========     ======        =========
Tier I (core) capital and ratio to
     risk-weighted total assets......         10.3%     $  215,849       4.0%       $  83,790        6.0%       $ 125,685
                                          ========                    ======        =========     ======        =========
Allowable Tier 2 capital:
General loan valuation allowances ...                       10,149
                                                        ----------
Total risk-based capital and ratio to
     risk-weighted total assets......         10.8%     $  225,998       8.0%       $ 167,580       10.0%       $ 209,475
                                          ========      ==========    ======        =========     ======        =========
Total assets.........................                   $3,045,981
                                                        ==========
Adjusted total assets................                   $3,041,980
                                                        ==========
Risk-weighted assets.................                   $2,094,753
                                                        ==========
                                       9
<page>
As of March 31, 2004 Stockholders'
     Equity and ratio to total assets          7.1%     $  229,583
                                          ========
Unrealized decrease in market value
     of assets available for sale
     (net of applicable income taxes)                       (1,652)
Goodwill.............................                       (5,559)
Disallowed servicing assets..........                         (123)
                                                        ----------
Tangible capital and ratio to
     adjusted total assets...........          6.9%     $  222,249       1.5%       $  48,449
                                          ========      ==========    ======        =========
Tier I (core) capital and ratio to
     adjusted total assets...........          6.9%     $  222,249       3.0%       $  96,898        5.0%       $ 161,496
                                          ========      ==========    ======        =========     ======        =========
Tier I (core) capital and ratio to
     risk-weighted total assets......         10.2%     $  222,249       4.0%       $  87,399        6.0%       $ 131,099
                                          ========      ==========    ======        =========     ======        =========
Allowable Tier 2 capital:
General loan valuation allowances ...                       10,749
                                                        ----------
Total risk-based capital and ratio to
     risk-weighted total assets......         10.7%     $  232,998       8.0%       $ 174,798       10.0%       $ 218,498
                                          ========      ==========    ======        =========     ======        =========
Total assets.........................                   $3,238,312
                                                        ==========
Adjusted total assets................                   $3,229,922
                                                        ==========
Risk-weighted assets.................                   $2,184,981
                                                        ==========


7.   EARNINGS PER SHARE

The  weighted-average  number  of shares  used to  calculate  basic and  diluted
earning per share,  including the  adjustments  for the stock  options,  for the
three months ended March 31, 2003 are as follows:


                                                                      For the Three Months Ended
                                                                           March 31, 2003
                                                               ---------------------------------------
                                                                  Income          Shares       Per-Share
                                                                 Numerator     Denominator       Amount
                                                               ========================================
                                                                                    
Net income.................                                    $ 5,117,000
Basic EPS:
Mortgage loans.............
Income available to
     common stockholders...                                    $  5,117,000     14,388,549    $     0.36
                                                               ============                   ==========
Effect of diluted shares:
     Common stock options..                                                       124,286
                                                                                  -------
Diluted EPS:
Income available to
     common stockholders...                                    $  5,117,000     14,512,835    $     0.35
                                                               ============     ==========    ==========

The  weighted-average  number  of shares  used to  calculate  basic and  diluted
earning per share,  including the  adjustments  for the Bank's stock options for
the three months ended March 31, 2004, are as follows:


                                                                     For the Three Months Ended
                                                                           March 31, 2004
                                                               ---------------------------------------
                                                                  Income          Shares       Per-Share
                                                                 Numerator     Denominator       Amount
                                                               ========================================
                                                                                     
Net income.................                                    $  5,687,000
Basic EPS:
Mortgage loans.............
Income available to
     common stockholders...                                    $  5,687,000     14,618,229    $     0.39
                                                               ============                   ==========
Effect of diluted shares:
     Common stock options..                                                       341,978
     MRP shares............                                                       156,295
                                                                                  -------
Diluted EPS:
Income available to
     common stockholders...                                    $  5,687,000     15,121,711    $     0.38
                                                               ============     ==========    ==========

                                       10
<page>


ESOP shares that have not been committed to be released are not considered to be
outstanding.

8.   OTHER COMPREHENSIVE INCOME (LOSS)

An analysis  of the  changes in  Accumulated  Other  Comprehensive  Loss for the
periods ended March 31, 2003 and 2004, is as follows:



                                                                              For the Three         For the Three
                                                                              Months Ended           Months Ended
                                                                             March 31, 2003         March 31, 2004
                                                                            ----------------       ---------------
                                                                               Unrealized             Unrealized
                                                                                 Losses                 Losses
                                                                              On Securities          On Securities
                                                                            ==========================================
                                                                                          (In Thousands)

                                                                                                      
  Beginning Balance..................................................         $  (3,535)                $ (2,717)
  Current-period change..............................................              (651)                   2,712
                                                                                   -----                   -----
  Ending balance.....................................................         $  (4,186)                 $   (5)
                                                                                  ======                   =====


An analysis of the related tax effects allocated to Other  Comprehensive  Income
(Loss) is as follows:



                                                For the Three Months Ended           For the Three Months Ended
                                                      March 31, 2003                       March 31, 2004
                                              --------------------------------     --------------------------------
                                              Before-tax    Tax     Net-of-Tax     Before-tax     Tax    Net-of-Tax
                                               Amount     Benefit    Amount         Amount     Benefit    Amount
                                              ========== ========== ========== === ========== ========== ==========

Unrealized gain (loss) on assets available for sale:
 Unrealized holding gains
     (losses) arising
                                                                                       
     during period........................... $(1,067)   $   416    $  (651)       $ 5,033    $(1,963)   $ 3,070
Reclassification adjustment
     for (gains) losses
     realized in net income.................       -          -          -            (587)       229       (358)
                                              --------   --------   --------       -------    --------   --------
Other comprehensive income (loss)...........  $(1,067)   $   416    $  (651)       $ 4,446    $(1,734)   $ 2,712
                                              =========  ========   =========      ========   =========  ========


9.             CONTINGENCIES

The Company is subject to various claims,  legal actions and complaints  arising
in the ordinary course of business. In the Company's opinion, the disposition of
these  matters  will  not  have a  material  adverse  effect  on  our  financial
condition, results of operations or cash flows.

                                       11


Item 2. Management's  Discussion and Analysis of Financial Condition and Results
     of Operations

                     MANAGEMENT'S DISCUSSION AND ANALYSIS OF
                  FINANCIAL CONDITION AND RESULTS OF OPERATIONS

General.

Fidelity  Bankshares,  Inc. (the  "Company")  is the parent  company of Fidelity
Federal Bank & Trust ("Fidelity Federal" or the "Bank"). The Company conducts no
business  other than  holding the common  stock of the Bank.  Consequently,  the
Company's net income is primarily  derived from the Bank.  The Bank's net income
is  primarily  dependent  on its net interest  income,  which is the  difference
between  interest  income  earned  on its  investments  in  mortgage  loans  and
mortgage-backed securities,  other investment securities and loans, and its cost
of funds consisting of interest paid on deposits and borrowings.  The Bank's net
income also is  affected by its  provision  for loan  losses,  as well as by the
amount of other  income,  including  income from fees and service  charges,  net
gains and losses on sales of investments, and operating expense such as employee
compensation and benefits,  deposit insurance premiums,  occupancy and equipment
costs, and income taxes. Earnings of the Bank also are affected significantly by
general  economic and  competitive  conditions,  particularly  changes in market
interest rates, government policies and actions of regulatory authorities, which
events are beyond the control of the Bank. In  particular,  the general level of
market interest rates tends to be highly cyclical.

Forward-Looking Statements.

When used in this  report,  the words or  phrases  "will  likely  result,"  "are
expected  to," "will  continue,"  "is  anticipated,"  "estimate,"  "project"  or
similar expressions are intended to identify "forward-looking statements" within
the  meaning of the  Private  Securities  Litigation  Reform  Act of 1995.  Such
statements  are subject to certain  risks and  uncertainties,  including,  among
other  things,  changes in economic  conditions  in the  Company's  market area,
changes in policies by  regulatory  agencies,  fluctuations  in interest  rates,
demand for loans in the Company's  market area and competition  that could cause
actual results to differ materially from historical earnings and those presently
anticipated  or projected.  The Company  wishes to caution  readers not to place
undue reliance on any such  forward-looking  statements,  which speak only as of
the date made.  The Company  wishes to advise  readers  that the factors  listed
above  could  affect the  Company's  financial  performance  and could cause the
Company's  actual  results  for  future  periods to differ  materially  from any
opinions or statements  expressed  with respect to future periods in any current
statements.

Other Comprehensive Operations.

The Company's  only  component of Other  Comprehensive  Operations for the three
months  ended  March 31, 2004 and 2003 is the change in the  unrealized  gain or
loss on assets available for sale.

Other comprehensive income for the quarter ended March 31, 2004 was $2.7 million
compared to other comprehensive loss of $651,000 for the quarter ended March 31,
2003. During the quarter ended March 31, 2004, the market value of the Company's
assets  available for sale  increased by $4.4  million,  which net of income tax
benefit of $1.7 million resulted in other comprehensive  income of $2.7 million.
During the  quarter  ended March 31,  2003,  the value of the  Company's  assets
available for sale decreased by $1.1 million which net of $416,000 in income tax
benefit resulted in other comprehensive loss of $651,000.

                                       12
<page>

Changes in Financial Condition.

The Company's  assets  increased by $192.6 million to $3.24 billion at March 31,
2004 from $3.05 billion at December 31, 2003. Cash and assets available for sale
increased  by $102.3  million,  while net loans  receivable  increased  by $88.9
million.  All other assets  increased by $1.4  million.  Funds were provided for
these  increases  in assets by an increase in  deposits  of $181.2  million,  an
increase in all other  liabilities  of $3.2 million and an increase in equity of
$8.2  million.  The  increase in equity is  primarily  due to net income of $5.7
million,  net of dividends  declared,  and an increase in unrealized increase in
market value of assets available for sale.

Results of Operations.

Net income for the quarter ended March 31, 2004 was $5.7 million, an increase of
$570,000  when  compared to $5.1  million for the quarter  ended March 31, 2003.
While net interest  income  after  provision  for loan losses  increased by $3.3
million,  this  increase  was  partially  offset by a decline in other income of
$548,000 and increases in operating  expense of $1.8  million,  together with an
increase in the provision for income taxes of $398,000.

Interest Income.

Interest  income for the quarter ended March 31, 2004  increased by $3.2 million
to $38.1  million,  representing  an increase of 9.3% when  compared to the same
quarter in 2003. Interest income from loans increased by $878,000.  Although the
average  balance of loans during the quarter  ended March 31, 2004  increased by
$273.1  million,  an increase of 14.0%  compared to the same quarter in 2003, to
$2.2 billion,  this was offset by a decline in interest rates on loans. Interest
income on  securities  increased by $2.6 million  during the quarter ended March
31, 2004 to $5.0  million,  an increase of 106.8%  compared to the quarter ended
March 31, 2003.  This increase is  attributable  to an increase of 110.9% in the
average balance of the Company's investments.

Interest Expense.

Interest expense for the quarter totaled $14.1 million,  an increase of $103,000
compared  to the  quarter  ended March 31,  2003.  Interest  expense on deposits
declined by $55,000 during the quarter ended March 31, 2004 compared to the same
quarter in 2003.  While the  average  balance of  deposits  increased  by $506.9
million, or 25.3%, to $2.5 billion, this increase was offset by a decline in the
cost of these  deposits  to 1.50%  during  the  quarter  ended  March 31,  2004,
compared to 1.89% during the quarter  ended March 31,  2003.  The decline in the
cost of deposits  is  principally  due to the  increase  in the  Company's  core
deposits,  consisting  of lower  costing  checking,  savings  and  money  market
accounts,  to 74.4% of all the company's  deposits at March 31, 2004 compared to
64.4% at March 31,  2003.  The  increase in interest  expense on  borrowings  of
$158,000 is  attributable  to  interest  expense on the  Company's  subordinated
debentures,  issued in connection with the Company's December, 2003, issuance of
$22.0 million in trust preferred securities.

Net Interest Income.

Net  interest  income for the quarter  ended March 31,  2004  increased  by $3.1
million to $23.9  million  compared to the quarter  ended March 31,  2003.  This
increase  was due to the  Company's  $3.2 million  increase in interest  income,
reduced by the $103,000 increase in interest expense.

                                       13
<page>

Provision for Loan Losses.

The  provision for loan losses was $596,000 for the quarter ended March 31, 2004
compared to $790,000 for the quarter  ended March 31, 2003.  The  provision  for
loan  losses is deemed  by  management  to be  adequate,  considering  the risks
inherent in the Bank's loan portfolio.  The ratio of valuation allowances to net
loans  receivable at March 31, 2004 and December 31, 2003 was 0.51%  compared to
0.46% at March 31, 2003.

Our financial  statements are prepared in accordance with accounting  principles
generally accepted in the United States of America and, accordingly,  allowances
for loan losses are based on management's estimate of the losses inherent in the
loan portfolio.  We provide both general valuation  allowances (for unspecified,
probable  losses) and specific  valuation  allowances  (for known losses) in our
loan portfolio. General valuation allowances are added to the Bank's capital for
purposes of computing the Bank's  regulatory  risk-based  capital.  We regularly
review our loan portfolio,  including  impaired loans, to determine  whether any
loans require  classification  or the  establishment  of  appropriate  valuation
allowances. Since we are increasing our origination of commercial business loans
and  commercial  real estate  mortgages  and since such loans are deemed to have
more credit risk than residential  mortgage loans, our provision for loan losses
is likely to increase in future periods.

Other Income.

Other income for the quarter ended March 31, 2004 was $6.5 million, reflecting a
$548,000 decline from $7.0 million for the quarter ended March 31, 2003.  Income
from service  charges on deposit  accounts  increased by $937,000 as a result of
the  increase  in the Bank's  core  deposits.  There was an increase in fees for
other banking services which reflects increased  commissions on insurance policy
sales and  appraisal  fees of  $378,000.  The  Company had gains on the sales of
securities  of $587,000  during the quarter ended March 31, 2004 for which there
were no  comparable  sales  during the same  quarter in 2003.  Offsetting  these
increases was a decline on income from loan sales of $2.5 million in the quarter
ended March 31, 2004,  compared to 2003. During the quarter ended March 31, 2003
the Bank  sold a $50  million  pool of loans  which  resulted  in a gain of $1.5
million.  There was no such  comparable  sale in 2004. In addition,  the Company
experienced a decline in other loan sales,  much of which is  attributable  to a
decline in  production  of 30 year fixed  rate  loans,  which were being sold to
minimize interest rate risk in the event of an increasing rate environment.

Operating Expense.

Operating  expense increased by $1.8 million to $20.5 million during the quarter
ended  March 31,  2004  compared to the same  quarter in 2003.  Of this  amount,
$594,000  relates to increased  occupancy and equipment  costs,  reflecting  the
Company's continued branch office and franchise expansion. Salaries and benefits
increased by $848,000, or 7.6%, which includes the additional personnel to staff
the branches as well as normal compensation increases.  The increase of $330,000
in  miscellaneous  expense  reflects  increased costs for telephone,  utilities,
office supplies,  general  insurance costs and armored car services to serve the
Bank's increased number of loan and deposit customers.

                                       14



Income Taxes.

The income tax  provision  was $3.6 million for the quarter ended March 31, 2004
compared to $3.2  million for the quarter  ended March 31, 2003.  The  provision
reflects the current  rates paid for Federal and State  income taxes  applied to
the Company's pre-tax income.  Item 3.  Quantitative and Qualitative  Disclosure
About Market Risk

Market Risk Analysis.

As a  holding  company  for  a  financial  institution,  the  Company's  primary
component of market risk is interest rate  volatility.  Fluctuations in interest
rates will ultimately  impact both the level of income and expense recorded on a
large portion of the Bank's assets and liabilities,  and the market value of all
interest-earning assets and interest-bearing liabilities, other than those which
possess  a  short  term  to  maturity.  Since  the  majority  of  the  Company's
interest-bearing  liabilities  and nearly all of the Company's  interest-earning
assets are held by the Bank,  virtually all of the Company's  interest rate risk
exposure lies at the Bank level. As a result, all significant interest rate risk
management  procedures  are performed by management of the Bank.  Based upon the
nature of the Bank's  operations,  the Bank is not  subject to foreign  currency
exchange or commodity  price risk.  The Bank's loan  portfolio  is  concentrated
primarily in Palm Beach, Martin and Broward Counties in Florida and is therefore
subject to risks  associated  with the local economy.  As of March 31, 2004, the
Company  does not own any trading  assets other than $1.3 million of assets held
by the SMPIAP Trust which can be actively traded by and are held for the benefit
of senior management.  Income in these accounts accrues to and losses are solely
absorbed by senior management.  At March 31, 2004, the Company does not have any
hedging transactions in place such as interest rate swaps and caps.

Asset and Liability Management-Interest Rate Sensitivity Analysis.

The  majority  of our assets  and  liabilities  are  monetary  in nature,  which
subjects us to significant  interest rate risk. As stated above, the majority of
our interest-bearing  liabilities and nearly all of our interest-earning  assets
are held by  Fidelity  Federal  Bank & Trust and,  therefore,  nearly all of our
interest rate risk is at the Fidelity Federal Bank & Trust level.

We monitor interest rate risk by various  methods,  including "gap" analysis and
analyzing  changes  in the net  present  value of our  assets,  liabilities  and
off-balance  sheet items (our net portfolio value or "NPV") which  analysis,  is
reviewed  with the Board of Directors on a quarterly  basis.  We use an internal
model  that  generates  estimates  of our NPV  over a  range  of  interest  rate
scenarios.  The model  calculates NPV  essentially by discounting the cash flows
from our assets and liabilities to present value using current market rates, and
adjusting those discount rates accordingly for various interest rate scenarios.

                                       15



The following table sets forth our estimated internal  calculations of NPV as of
March 31, 2004, for  instantaneous and parallel shifts in the yield curve in 100
basis point  increments up and down.  Due to the low interest  rate  environment
that existed at March 31, 2004, an analysis of a 200 basis point  downward shift
in interest rates is not shown.

       Changes in Rates                  Market Value of Portfolio Equity
         (Rate Shock)               $  Amount        $ Change         % Change
         ============             =============================================
                                                 (Dollars in Thousands)

   +200bp                           $ 321,074        $ (76,665)         (19.3)%

   +100bp                             361,079          (36,660)         ( 9.2)%
     -0-                              397,739                0            0.0%
   -100bp                             371,105          (26,634)          (6.7)%


Fidelity Federal Bank & Trust's internal calculation of NPV at December 31, 2003
shows the negative  effects of rate caps and floors in certain  interest earning
assets and particularly  interest bearing liabilities in both rising and falling
interest rate  scenarios.  As shown in the previous  table,  NPV was  negatively
affected in both rising and falling rate scenarios as a result of these interest
rate caps and  floors.  In  preparing  the NPV table  above,  we have  estimated
prepayment rates for our loans ranging from 8% to 30%, depending on the interest
rate scenario and loan type. These rates are management's best estimate based on
prior repayment experience.

In preparing  the NPV table above,  the Company  makes  various  assumptions  to
determine the net portfolio value at the assumed changes in interest rate. These
assumptions include loan prepayment rates, deposit decay rates and market values
of certain assets and  liabilities  under the various  interest rate  scenarios.
While  management  believes these  assumptions to be reasonable  there can be no
assurance that our assets and liabilities  would be impacted as indicated in the
table  above.  Certain  shortcomings  are  inherent in any  methodology  used in
interest rate risk measurements.  Modeling changes in NPV requires the making of
certain  assumptions  that may or may not  reflect  how actual  yields and costs
respond to changes in market rates.  For example,  although  certain  assets and
liabilities may have similar maturities or periods to repricing,  they may react
in different degrees to changes in market interest rates.  Also,  interest rates
on certain  types of assets and  liabilities  may fluctuate in advance of or lag
behind changes in market interest rates.  Additionally,  certain assets, such as
ARM loans, have features that restrict changes in interest rates on a short-term
basis  and over the life of the  assets.  Moreover,  in the event of a change in
interest  rates,  prepayment and early  withdrawal  levels may possibly  deviate
significantly from those assumed in calculating the above table.  Management has
also  made  estimates  of fair  value  discount  rates  that it  believes  to be
reasonable.  However, due to the fact that there is no quoted market for many of
the assets and  liabilities,  management  has no  definitive  basis to determine
whether the fair values presented would be indicative of the value negotiated in
an actual sale.

Accordingly,  while the above table provides an estimate of the Bank's  interest
rate risk exposure at a particular  point in time, it is not intended to provide
a precise  forecast  of the  effect of market  changes on the Bank's NPV and net
interest income, as actual results may vary.

Under OTS risk-based capital  regulations,  savings associations are required to
calculate  the  NPV.  These   calculations   are  based  upon  data   concerning
interest-earning assets,  interest-bearing  liabilities and other rate sensitive
assets and  liabilities  provided  to the OTS on schedule  CMR of the  quarterly

                                       16
<page>

Thrift  Financial  Report.  Commencing  September  30,  1994,  for  purposes  of
measuring  interest rate risk,  the OTS began using the NPV  calculations  which
essentially discount the cash flows from an institution's assets and liabilities
to present value, using current market rates. There are differences  between the
Bank's internal  assumptions used to calculate the previously  presented NPV and
those used by the OTS. For example, the Bank's internally calculated decay rates
for certain NOW, passbook and money market accounts produces an average expected
life for these  instruments which is longer than the average expected life using
the OTS standard assumptions for these same instruments. Accordingly, the Bank's
previously presented NPV calculations are not representative of those that would
be produced by the OTS.

The Bank's  policy in recent  years has been to reduce its  exposure to interest
rate risk  generally by better  matching  the  maturities  of its interest  rate
sensitive  assets  and  liabilities  and by  originating  ARM  loans  and  other
adjustable  rate  or  short-term  loans,  as well  as by  purchasing  short-term
investments. However, particularly in a low interest rate environment, borrowers
typically  prefer  fixed  rate  loans to ARM  loans.  The Bank does not  solicit
high-rate jumbo certificates or brokered funds.

The table below provides  information about the Company's financial  instruments
that are  sensitive  to changes in  interest  rates.  As shown in the  following
table, the Company's  cumulative one-year interest rate sensitivity gap at March
31, 2004 was a positive 22.19%.




                                                                          More Than One    More Than Three
                                     Within Three        Four to Twelve   Year to Three    Years to Five     Over Five
                                         Months             Months           Years            Years            Years
                                     ---------------------------------------------------------------------------------
                                                                     (Dollars in Thousands)

Interest-earning assets (1):
   Residential mortgage loans: (2)
                                                                                              
     Fixed rate........................  $  56,397      $  125,057        $ 230,082          $  138,144      $ 187,111
     Adjustable rate...................    100,500         189,270          128,641             142,518             --

   Commercial mortgage loans: (2)
     Fixed rate........................      9,946          19,447           26,332              14,036         16,556

     Adjustable rate...................    220,926         358,293            3,873               3,884             --
   Other loans (2)
         Fixed rate....................     15,940          22,061           31,218              10,062          6,053
     Adjustable rate...................    219,837          17,345               --                  --             --
   Mortgage-backed securities
     Fixed rate........................      8,331          23,326           41,848              24,947          32,171
     Adjustable rate...................    147,946          13,560           26,265              24,625          17,141
   Municipal bonds and government and
   agency securities - fixed rate......        --            5,255          117,110                  --          20,162
 Other interest earning assets -
      adjustable                         $  205,224              --              --                  --              --
                                         ==========        ========        =========           =========        ========
           Total                            985,047        773,614        $ 605,369           $ 325,216        $ 279,194
                                         ==========        ========        =========          ==========        ========

Interest-bearing liabilities
   Deposits: (3)
   Checking and funds transfer accounts  $   49,690       $154,349        $ 224,186           $ 112,932        $ 382,983
   Passbook accounts.................        31,521        109,357          182,471              96,096          246,574
   Money market accounts.............        30,699         99,294          119,848              45,874           66,216
   Certificate accounts (4)..........       105,478        359,753          168,152              44,067               --
Borrowings: (4)......................        64,743         34,800          152,518              70,419           29,776
                                           ---------       --------        --------           ---------        ---------

                  Total                  $  282,131       $757,553          847,175             369,387        $ 725,549
                                          ==========      ========         ========           =========        =========

Excess (deficiency) of interest-earning
     assets over interest-bearing
     liabilities.....................    $  702,916       $ 16,061        $(241,806)            (11,171)        (446,355)
                                         ==========       ========        ==========          =========        =========

Cumulative excess of interest-earning
     assets over interest-bearing
     liabilities.....................    $  702,916       $718,977        $ 477,171          $ 466,000         $  19,645
                                          =========       =========         =======          =========         =========

  Cumulative excess of interest-earning
      assets over interest-bearing liabilities
      as a percent of total assets            21.69%         22.19%           14.72%             14.38%             0.61%
                                              =====          =====            =====              =====              ====


                                       17
<page>

(1)  Adjustable  and  floating  rate assets are  included in the period in which
     interest  rates are next  scheduled to adjust  rather than in the period in
     which they are due.  Fixed rate assets are included in the periods in which
     they are  scheduled to be repaid based on scheduled  amortization.  In both
     cases,  amounts are  adjusted to reflect  estimated  prepayments.  For this
     table,  all  loans  and  mortgage-backed  securities  were  assigned  a 20%
     prepayment rate.
(2)  Balances  are  shown  net of  loans in  process  and are not  adjusted  for
     premiums, discounts, reserves and unearned fees.
(3)  All of the  Company's  non-certificate  deposits are  generally  subject to
     immediate withdrawal.  However,  management considers a significant portion
     of these accounts to be core deposits  having longer  effective  maturities
     based on the Company's actual retention of such deposit accounts in various
     interest  rate  environments.  In  the  year  2001,  we  contracted  with a
     third-party  consultant to perform an analysis of the core deposit accounts
     to obtain an estimate of the actual  deposit  balance  trends over  various
     interest  rates  scenarios  over the previous five years.  We then used the
     information  obtained to provide a forecast of future  balance  trends.  We
     then used the information  obtained to provide a forecast of future balance
     trends.  Management  does not feel that the  deposit  trends  have  changed
     materially since 2001.
(4)  Certificate  accounts and Borrowings are assumed to have no prepayments and
     are shown in the period in which they contractually mature.

Certain  shortcomings are inherent in any methodology used to calculate interest
rate sensitivity.  The asset prepayment speed and deposit decay rate assumptions
are based on past  experience  and should not be regarded as  indicative  of the
actual  prepayments and withdrawals that may be experienced in any given period.
In the event of changes in interest rates, prepayment and early withdrawal would
possibly  deviate  significantly  from those  assumed in  calculating  the above
table. Also, although certain assets and liabilities may have similar maturities
or  periods  to  repricing,  they may react  differently  to  changes  in market
interest  rates.  Certain  assets such as adjustable  rate  mortgage  loans have
features that restrict  changes in interest rates on a short term basis and over
the life of the asset.

In recent years our policy has been to reduce our exposure to interest rate risk
generally by better  matching the  maturities  of our  interest  rate  sensitive
assets and  liabilities,  and by originating ARM loans and other adjustable rate
or short-term loans, as well as by purchasing short-term  investments.  However,
particularly in a  low-interest-rate  environment,  borrowers  typically  prefer
fixed-rate loans to ARM loans. We do not solicit high-rate jumbo certificates or
brokered funds.

Liquidity and Capital Resources.

The Bank is required to maintain  minimum  levels of liquid assets as defined by
OTS regulations. This requirement, which varies from time to time depending upon
economic  conditions and deposit  flows,  is based upon a percentage of deposits
and short-term borrowings. The Bank's liquidity ratio averaged 12.72% during the
month of March 31, 2004.  Liquidity ratios averaged 11.47% for the quarter ended
March 31, 2004.  The Bank adjusts its liquidity  levels in order to meet funding
needs of loan  originations,  deposit outflows,  payment of real estate taxes on
mortgage loans, and repayment of borrowings and loan commitments.  The Bank also
adjusts  liquidity as  appropriate  to meet its asset and  liability  management
objectives.

The Bank's primary sources of funds are deposits, amortization and prepayment of
loans and mortgage-backed  securities and other short-term investments,  as well
as earnings  and funds  provided  from  operations.  While  scheduled  principal
repayments on loans and mortgage-backed  securities are a relatively predictable
source of funds,  deposit flows and loan  prepayments are greatly  influenced by
general interest rates,  economic  conditions and competition.  The Bank manages
the pricing of its deposits to maintain a desired deposit balance.  In addition,
the Bank invests excess funds in short-term  interest-earning  and other assets,
which   provide   liquidity   to   meet   lending    requirements.    Short-term
interest-bearing deposits with the FHLB of Atlanta amounted to $192.2 million at
March 31,  2004.  Other  assets  qualifying  for  liquidity  at March 31,  2004,
including  unpledged  mortgage-backed   securities  guaranteed  by  the  Federal
National  Mortgage  Association and the Federal Home Loan Mortgage  Corporation,
were  $193.6  million.  For  additional  information  about  cash flows from the
Company's  operating,   financing  and  investing   activities,   see  Unaudited
Consolidated  Statements of Cash Flows  included in the  Unaudited  Consolidated
Financial  Statements.  The primary  sources of cash are net  income,  principal
repayments  on  loans  and  mortgage-backed  securities,  increases  in  deposit
accounts and advances from the FHLB.

                                       18
<page>

Liquidity  management  is  both a  daily  and  long-term  function  of  business
management.  If the Bank  requires  funds  beyond its ability to  generate  them
internally, borrowing agreements exist with the FHLB which provide an additional
source of funds. At March 31, 2004, the Bank had $261.1 million in advances from
the FHLB. At March 31, 2004, the Bank had  commitments  outstanding to originate
or purchase loans of $270.3  million.  This amount does not include the unfunded
portion of loans in process. Certificates of deposit scheduled to mature in less
than  one  year at  March  31,  2004  totaled  $465.1  million.  Based  on prior
experience, management believes that a significant portion of such deposits will
remain with the Bank. Contractual Obligations and Commercial Commitments

Our long-term debt,  which in the aggregate  totals $313.4 million,  consists of
obligations to the FHLB totaling $261.1 million and $52.3 million in obligations
resulting from the issuance of trust preferred  securities from Fidelity Capital
Trust I in January 1998 as well as Fidelity  Capital Trust II in December  2003.
The  obligations  arising  from  the  issuance  of trust  preferred  securities,
presented as Guaranteed  Preferred Beneficial Interests in Company Debentures in
our balance  sheet at March 31,  2004 are due in the amount of $29.6  million in
January,  2028 and $22.7 million in January 2034. In addition, we have leasehold
obligations totaling $16.4 million. These contractual  obligations are set forth
in the table below as of March 31, 2004.

The tables below summarize the Company's contractual obligations, commercial and
other commitments at March 31 2004.




                                                         Less Than                                         After 5
                                          Total           1 year         1-3 Years        3-5 Years         Years
                                          ------------------------------------------------------------------------
                                                                      (In Thousands)
                                                                                        
Long-term Debt(1)................       $313,427        $ 38,774         $152,417        $ 69,717         $ 52,519
Capital Lease Obligations........             --              --               --              --               --
Operating Lease Obligations......         16,404           1,585            3,132           2,978            8,709
                                      ----------      ----------       ----------      ----------       ----------
Total Contractual Cash Obligations    $  329,831      $   40,359         $155,549        $ 72,695         $ 61,228
                                      ==========      ==========       ==========      ==========       ==========



(1)  Includes advances from the Federal Home Loan Bank and Guaranteed  Preferred
     Beneficial Interests in Debentures.

Commercial and Other Commitments



                                                         Less Than                                         After 5
                                          Total           1 year         1-3 Years        3-5 Years         Years
                                          ------------------------------------------------------------------------
                                                                      (In Thousands)

                                                                                        
Lines of Credit(1)...............       $183,734        $  5,068         $  9,015        $ 31,675         $137,976
Standby Letters of Credit........          8,135           7,109            1,026              --               --
Other Commercial Commitments.....        136,268         136,268               --              --               --
Other Commitments................        115,782         115,782               --              --               --
                                      ----------      ----------       ----------      ----------       ----------
Total Contractual Cash Obligations    $  443,919      $  264,227         $ 10,041        $ 31,675         $137,976
                                      ==========      ==========       ==========      ==========       ==========


(1)  Includes $145.3 million in undisbursed lines of credit.

New Accounting Pronouncements

In December  2002,  the FASB issued SFAS No. 148,  "Accounting  for  Stock-Based
Compensation-Transition  and Disclosure, an amendment of FASB Statement No. 123"
to provide  alternative methods of transition for a voluntary change to the fair
value based method of  accounting  for  stock-based  employee  compensation.  In
addition,  this statement amends the disclosure requirements of Statement 123 to
require prominent  disclosures in both annual and interim  financial  statements
about the method of accounting for  stock-based  employee  compensation  and the
effect of the method used on reported  results.  The provisions of Statement 148
are effective for interim periods  beginning after December 15, 2002, with early
application  encouraged.  The adoption of the disclosure  provisions of SFAS No.
148 did not have a material  effect on the  Company's  results of  operations or
financial  position.  The  disclosures  pursuant to SFAS No. 148 may be found in
Note 2.

                                       19

<page>
In January 2003,  the FASB issued FIN 46,  "Consolidation  of Variable  Interest
Entities" which addresses  consolidation of variable  interest entities ("VIEs")
certain of which are also referred to as special purpose entities ("SPEs").  The
FASB  revised  FIN 46 in  December  2003.  VIEs are  entities  in  which  equity
investors do not have the characteristics of a controlling financial interest or
do not have  sufficient  equity at risk for the entity to finance its activities
without additional  subordinated financial support from other parties. Under the
provisions  of FIN 46, a company is to  consolidate  a VIE if the  company has a
variable  interest (or  combination  of variable  interests)  that will absorb a
majority of the VIE's expected  losses if they occur,  receive a majority of the
VIE's expected  residual returns if they occur, or both. The  implementation  of
FIN 46 is required for public  entities at the end of the first  interim  period
ending after March 15, 2004 if the VIE was created before February 1, 2003, with
early adoption  allowed,  and immediately for entities created after February 1,
2003.  The Company  early  adopted FIN 46 and has  deconsolidated  the  Fidelity
Capital Trust I at December 31, 2003. The  deconsolidation  of Fidelity  Capital
Trust I did not have a material impact on the Company's  consolidated  financial
position or results of operations.

On May 15, 2003, the FASB issued SFAS No. 150, "Accounting for Certain Financial
Instruments with  Characteristics  of Both Liabilities and Equity." SFAS No. 150
was effective May 31, 2003 for all new and modified  financial  instruments  and
otherwise effective at the beginning of the first interim period beginning after
June 15,  2003.  SFAS No. 150  changes  the  accounting  for  certain  financial
instruments  that,  under previous  guidance,  issuers could be accounted for as
equity.   SFAS  No.  150  requires  that  those  instruments  be  classified  as
liabilities  or in  some  circumstances  assets.  In  November  2003,  the  FASB
indefinitely  deferred the effective date for the classification and measurement
provisions of certain mandatorily redeemable noncontrolling interests under SFAS
No. 150. The adoption of this  statement  did not have a material  impact on the
Company's results of operations or financial conditions.

In November 2003,  the EITF reached a consensus on the disclosure  provisions of
EITF Issue No. 03-1,  "The Meaning of  Other-Than-Temporary  Impairment  and its
Application  to  Certain  Investments."  EITF No.  03-1  requires  that  certain
quantitative  and  qualitative  disclosures be made for certain debt  securities
classified as  available-for-sale  under SFAS No. 115,  "Accounting  for Certain
Investments  in Debt and Equity  Securities,"  that are  impaired at the balance
sheet  date  but for  which  an  other-than-temporary  impairment  has not  been
recognized.  Debt securities  within the scope of EITF Issue No. 99-20,  are not
subject to these disclosure provisions.  The disclosures are required for fiscal
years ending after  December 15, 2003, and  accordingly  the Company has adopted
the disclosure provisions of EITF No. 03-1 for the year ended December 31, 2003.

In December 2003, the FASB Issued  Statement of Financial  Accounting  Standards
No.  132  (revised  2003),  "Employees  Disclosures  about  Pensions  and  Other
Postretirement Benefits," an amendment of FASB Statements No. 87, 88 and 106, to
address  the  increasing  significance  of  corporate  pension  plans to company
financial statements and the call for greater transparency in financial reports.
The statement requires additional disclosures, regarding plan assets, investment
strategy,  measurement date, plan obligations,  cash flows and components of net
periodic benefit cost of defined benefit pension plans and other  postretirement
benefit  plans.  However,  it does not change the  measurement or recognition of
those plans  required by SFAS No. 87, SFAS No. 88 and SFAS No. 106.  The Company
has  adopted  the  disclosure  provisions  of EITF No.  03-1 for the year  ended
December 31, 2003.

                                       20
<page>

Item 4.       Controls and Procedures

(a)  Evaluation of disclosure controls and procedures.

Under the supervision and with the  participation  of our management,  including
our Chief  Executive  Officer and Chief  Financial  Officer,  we  evaluated  the
effectiveness  of the  design  and  operation  of our  disclosure  controls  and
procedures (as defined in Rule  13a-15(e) and 15d-15(e)  under the Exchange Act)
as of the end of the  fiscal  year  (the  "Evaluation  Date").  Based  upon that
evaluation,  the Chief Executive  Officer and Chief Financial  Officer concluded
that, as of the Evaluation  Date, our  disclosure  controls and procedures  were
effective in timely alerting them to the material information relating to us (or
our  consolidated  subsidiaries)  required to be included  in our  periodic  SEC
filings.

(b)  Changes in internal controls.

There were no  significant  changes  made in our  internal  controls  during the
period covered by this report or, to our knowledge,  in other factors that could
significantly affect these controls subsequent to the date of their evaluation.

See the  Certifications  pursuant  to Section 302 of the  Sarbanes-Oxley  Act of
2002.


                                       21

<page>


                            FIDELITY BANKSHARES, INC.
                                 AND SUBSIDIARY

                           Part II - Other Information


Item 1    Legal Proceedings

          There are various claims and lawsuits in which Fidelity Federal Bank &
          Trust is periodically involved incident to our business. Other than as
          set forth below, we believe these legal proceedings, in the aggregate,
          are not material to our financial condition or results of operations.

          On July 1, 2003,  Fidelity Federal Bank & Trust was named as defendant
          in the lawsuit, James Kehoe v. Fidelity Federal Bank & Trust, filed in
          the United States District Court for the Southern District of Florida.
          In this action, James Kehoe ("Kehoe"),  on behalf of himself and other
          similarly situated persons, has alleged that Fidelity Federal violated
          the Driver  Privacy  Protection Act by obtaining  driver  registration
          information  from  the  State  of  Florida  for  use in its  marketing
          efforts.  Kehoe seeks as damages the  statutory  minimum of $2,500 per
          violation.  As a  result  of  Kehoe's  suing on  behalf  of a class of
          plaintiffs,  the  potential  award,  should  Kehoe  prevail,  would be
          material.  At this time,  however,  the size of the class has not been
          asserted by Kehoe.  Fidelity  Federal is  currently  in the process of
          drafting a response to the  complaint  and discovery has only recently
          commenced.   Fidelity  Federal,  in  consultation  with  counsel,  has
          concluded  that the  lawsuit is  without  merit and  Fidelity  Federal
          intends to vigorously defend against Kehoe's claim.

          On  December  31,  2003,  Fidelity  Federal  Bank & Trust was named as
          defendant in two  lawsuits,  Kenneth A. Welt, as Chapter 7 Trustee vs.
          Fidelity  Federal Bank & Trust.  The two lawsuits have been brought by
          the same  plaintiff  in the Circuit  Court in the  Fifteenth  Judicial
          Circuit  in and for Palm Beach  County  and also in the United  States
          Bankruptcy  Court  Southern  District  of  Florida,  West  Palm  Beach
          Division.  The plaintiff has alleged that the Bank knew or should have
          known  that the  bankrupt  Thomas  Abrams  through  various  corporate
          plaintiffs,   including   The  Phoenix   Financial   Group,   Phoenix,
          Administrative  Services,  Inc. and Swiss Capital Management Ltd., was
          operating a "Ponzi Scheme". Fidelity Federal is seeking to consolidate
          the two  lawsuits  in the United  States  Bankruptcy  Court.  Fidelity
          Federal has filed an answer to the complaints. The plaintiff seeks (i)
          an accounting of all fees,  commissions  and other income  received by
          the Bank as a result of Thomas Abrams'  actions,  and damages for such
          amounts,  plus interest and costs in United States  Bankruptcy  Court,
          (ii) and  seeks  relief  of  unspecified  compensatory  damages,  plus
          interest  and  costs  in  the  Circuit  Court.  Fidelity  Federal,  in
          consultation  with counsel,  has concluded that the claims made by the
          plaintiff on behalf of the bankrupt  corporation are without merit and
          the Bank intends to vigorously defend itself in the two suits.

          On  February  18,  2004,  Fidelity  Federal  Bank & Trust was named as
          defendant in a lawsuit  William Adams et al., vs.  Thomson  Financial,
          Inc.,  Fidelity  Federal  Bank &  Trust,  N.A.,  Fidelity  Investments
          Services,  L.L.C.,  d/b/a  Fidelity  Investments,  National  Financial
          Services,  L.L.C., f/k/a National Financial Services Corporation,  Zoe

                                       22
   <page>
          Marrero, filed in the Fifteenth Judicial Circuit in and for Palm Beach
          County,  Florida. The plaintiffs in this case have alleged against the
          various  defendants  causes of action which arise from their investing
          in various Abrams  entities,  based upon the same factual  allegations
          set forth in  Kenneth  A.  Welt,  as  Chapter 7 Trustee  vs.  Fidelity
          Federal Bank & Trust. Fidelity Federal is named in one cause of action
          alleging  aiding and abetting  breaches of fiduciary duty. The various
          allegations are based upon Fidelity  Federal allowing Abrams to set up
          accounts with Fidelity  Federal,  deposit  monies in them,  issue bank
          checks based upon the deposits and generally offer banking services to
          the Abrams entities. Additionally, there are allegations that Fidelity
          Federal  solicited  clients  for the  Abrams  entities  and  pressured
          clients  to place  deposits  with the  Abrams  entities  and  Fidelity
          Federal.  There is no  specific  request for  damages,  other than the
          jurisdictional amount of in excess of $15,000.

          Fidelity  Federal has not yet answered the  complaint,  but intends to
          vigorously  defend itself.  Fidelity  Federal,  in  consultation  with
          counsel,  has  concluded  that the claims made by the  plaintiffs  are
          without merit.

Item 2    Changes in Securities and Stock Repurchases

              None.

Item 3    Default Upon Senior Securities

              Not applicable.

Item 4    Submission of Matters to a Vote of Security Holders

              None

Item 5    Other Information

              None.

Item 6    Exhibits and Reports on Form 8-K

              31.1  302 Certification

              31.2  302 Certification

              32.1  906 Certification

On January 20,  2004 the Company  filed a Form 8-K to report its fiscal year end
earnings.

                                       23
<page>


Item 6        Exhibits 31.1, 31.2 and 32.1

Certification  of  Chief  Executive  Officer  Pursuant  to  Section  302  of the
Sarbanes-Oxley Act of 2002

I, Vince A. Elhilow, President and Chief Executive Officer, certify that:


1.   I have reviewed this Quarterly Report on Form 10-Q of Fidelity  Bankshares,
     Inc.;

2.   Based on my knowledge, this report does not contain any untrue statement of
     a material  fact or omit to state a  material  fact  necessary  to make the
     statements made, in light of the circumstances  under which such statements
     were made, not misleading with respect to the period covered by this annual
     report;

3.   Based on my  knowledge,  the  financial  statements,  and  other  financial
     information  included  in  this  report,  fairly  present  in all  material
     respects the financial  condition,  results of operations and cash flows of
     the registrant as of, and for, the periods presented in this report;

4.   The  registrant's  other  certifying  officers  and I are  responsible  for
     establishing and maintaining disclosure controls and procedures (as defined
     in Exchange Act Rules 13a-15(e) and 15d-15(e)) for the registrant and have:


     a)   designed  such  disclosure  controls  and  procedures  or caused  such
          disclosure   controls  and   procedures  to  be  designed   under  our
          supervision,  to ensure  that  material  information  relating  to the
          registrant,  including its consolidated subsidiaries, is made known to
          us by others within those entities,  particularly during the period in
          which this report is being prepared;

     b)   evaluated the  effectiveness of the registrant's  disclosure  controls
          and procedures and presented in this report our conclusions  about the
          effectiveness of the disclosure controls and procedures, as of the end
          of the period covered by this report based on such evaluation; and

     c)   disclosed  in this  report  any  change in the  registrant's  internal
          control over financial reporting that occurred during the registrant's
          most recent fiscal quarter (the registrant's  fourth fiscal quarter in
          the case of an annual  report)  that has  materially  affected,  or is
          reasonably  likely to materially  affect,  the  registrant's  internal
          control over financial reporting;

5.   The registrant's other certifying  officers and I have disclosed,  based on
     our most recent evaluation of internal control over financial reporting, to
     the registrant's  auditors and the audit committee of registrant's board of
     directors (or persons performing the equivalent functions):


     a)   all significant  deficiencies and material weaknesses in the design or
          operation  of internal  control  over  financial  reporting  which are
          reasonably  likely to  adversely  affect the  registrant's  ability to
          record, process, summarize and report financial information; and

     b)   any fraud, whether or not material,  that involves management or other
          employees who have a  significant  role in the  registrant's  internal
          control over financial reporting;




May 7, 2004                                /s/ Vince A. Elhilow
- ------------                               -----------------------------------
Date                                       Vince A. Elhilow
                                           President and Chief Executive Officer


<page>

Certification  of  Chief  Financial  Officer  Pursuant  to  Section  302  of the
Sarbanes-Oxley Act of 2002

I, Richard D. Aldred,  Executive Vice  President,  Chief  Financial  Officer and
Treasurer, certify that:


1.   I have reviewed this Quarterly Report on Form 10-Q of Fidelity  Bankshares,
     Inc.;

2.   Based on my knowledge, this report does not contain any untrue statement of
     a material  fact or omit to state a  material  fact  necessary  to make the
     statements made, in light of the circumstances  under which such statements
     were made, not misleading with respect to the period covered by this annual
     report;

3.   Based on my  knowledge,  the  financial  statements,  and  other  financial
     information  included  in  this  report,  fairly  present  in all  material
     respects the financial  condition,  results of operations and cash flows of
     the registrant as of, and for, the periods presented in this report;

4.   The  registrant's  other  certifying  officers  and I are  responsible  for
     establishing and maintaining disclosure controls and procedures (as defined
     in Exchange Act Rules 13a-15(e) and 15d-15(e)) for the registrant and have:


     a)   designed  such  disclosure  controls  and  procedures  or caused  such
          disclosure   controls  and   procedures  to  be  designed   under  our
          supervision,  to ensure  that  material  information  relating  to the
          registrant,  including its consolidated subsidiaries, is made known to
          us by others within those entities,  particularly during the period in
          which this report is being prepared;

     b)   evaluated the  effectiveness of the registrant's  disclosure  controls
          and procedures and presented in this report our conclusions  about the
          effectiveness of the disclosure controls and procedures, as of the end
          of the period covered by this report based on such evaluation; and

     c)   disclosed  in this  report  any  change in the  registrant's  internal
          control over financial reporting that occurred during the registrant's
          most recent fiscal quarter (the registrant's  fourth fiscal quarter in
          the case of an annual  report)  that has  materially  affected,  or is
          reasonably  likely to materially  affect,  the  registrant's  internal
          control over financial reporting;

5.   The registrant's other certifying  officers and I have disclosed,  based on
     our most recent evaluation of internal control over financial reporting, to
     the registrant's  auditors and the audit committee of registrant's board of
     directors (or persons performing the equivalent functions):


     a)   all significant  deficiencies and material weaknesses in the design or
          operation  of internal  control  over  financial  reporting  which are
          reasonably  likely to  adversely  affect the  registrant's  ability to
          record, process, summarize and report financial information; and

     b)   any fraud, whether or not material,  that involves management or other
          employees who have a  significant  role in the  registrant's  internal
          control over financial reporting;



May 7, 2004                                         /s/ Richard D. Aldred
- ------------                                         ---------------------------
Date                                                 Richard D. Aldred
                                                     Executive Vice President,
                                                     Chief Financial Officer




EXHIBIT 32.1

                  CERTIFICATION OF CHIEF EXECUTIVE OFFICER AND
                             CHIEF FINANCIAL OFFICER
                         PURSUANT TO SECTION 906 OF THE
                           SARBANES-OXLEY ACT OF 2002




                                                                   Exhibit 32.1

                            Certification pursuant to
                             18 U.S.C. Section 1350,
                             as adopted pursuant to
                  Section 906 of the Sarbanes-Oxley Act of 2002

Vince A. Elhilow,  President and Chief Executive  Officer and Richard D. Aldred,
Executive  Vice  President,  Chief  Financial  Officer and Treasurer of Fidelity
Bankshares,  Inc. (the  "Company") each certify in his capacity as an officer of
the Company that he has  reviewed the annual  report of the Company on Form 10-Q
for the fiscal ended March 31, 2004 and that to the best of his knowledge:

(1)  the report fully  complies with the  requirements  of Sections 13(a) of the
     Securities Exchange Act of 1934; and


(2)  the information  contained in the report fairly  presents,  in all material
     respects, the financial condition and results of operations.

The purpose of this  statement  is solely to comply  with Title 18,  Chapter 63,
Section  1350 of the United  States  Code,  as  amended  by  Section  906 of the
Sarbanes-Oxley Act of 2002.


May 7, 2004                                /s/ Vince A. Elhilow
- -------------                              -------------------------------------
Date                                       President and Chief Executive Officer


May 7, 2004                                /s/ Richard D. Aldred
- -------------                              ------------------------------------
Date                                       Executive Vice President,
                                           Chief Financial Officer and Treasurer




<page>




                                   SIGNATURES


Pursuant  to the  requirements  of the  Securities  Exchange  Act of  1934,  the
Registrant has duly caused this report to be signed by the undersigned thereunto
duly authorized.



                                                     FIDELITY BANKSHARES, INC.






Date:  May 7, 2004                     By: /s/Vince A. Elhilow
                                           -------------------------------------
                                           Vince A. Elhilow
                                           President and Chief Executive Officer





Date:  May 7, 2004                     By: /s/Richard D. Aldred
                                           -------------------------------------
                                           Richard D. Aldred
                                           Executive Vice President
                                           Chief Financial Officer