We present the results of first dual-beam observations with VERA (VLBI Exploration of Radio Astrometry). The first dual-beam observations of a pair of H2O maser sources W49N and OH43.8-0.1 have been carried out on 2002 May 29 and July 23, and fringes of H2O maser lines at 22 GHz have been successfully detected. While the residual fringe phases of both sources show rapid variations over 360 degree due to the atmospheric fluctuation, the differential phase between the two sources remains constant for 1 hour with r.m.s. of 8 degree, demonstrating that the atmospheric phase fluctuation is removed effectively by the dual-beam phase referencing. The analysis based on Allan standard deviation reveals that the differential phase is mostly dominated by white phase noise, and the coherence function calculated from the differential phase shows that after phase referencing the fringe visibility can be integrated for arbitrarily long time. These results demonstrate VERA's high capability of phase referencing, indicating that VERA is a promising tool for phase referencing VLBI astrometry at 10 microarcsec level accuracy.