Any state of matter is classified according to its order, and the type of order that a physical system can possess is profoundly affected by its dimensionality. Conventional long-range order, as in a ferromagnet or a crystal, is common in three-dimensional systems at low temperature. However, in two-dimensional systems with a continuous symmetry, true long-range order is destroyed by thermal fluctuations at any finite temperature. Consequently, for the case of identical bosons, a uniform two-dimensional fluid cannot undergo Bose-Einstein condensation, in contrast to the three-dimensional case. However, the two-dimensional system can form a 'quasi-condensate' and become superfluid below a finite critical temperature. The Berezinskii-Kosterlitz-Thouless (BKT) theory associates this phase transition with the emergence of a topological order, resulting from the pairing of vortices with opposite circulation. Above the critical temperature, proliferation of unbound vortices is expected. Here we report the observation of a BKT-type crossover in a trapped quantum degenerate gas of rubidium atoms. Using a matter wave heterodyning technique, we observe both the long-wavelength fluctuations of the quasi-condensate phase and the free vortices. At low temperatures, the gas is quasi-coherent on the length scale set by the system size. As the temperature is increased, the loss of long-range coherence coincides with the onset of proliferation of free vortices. Our results provide direct experimental evidence for the microscopic mechanism underlying the BKT theory, and raise new questions regarding coherence and superfluidity in mesoscopic systems.