An analysis of the variability of wave climate and energy within the Black Sea for the period 1960–2011 was made using field data from the Voluntary Observing Ship Program. Methods using wavelet analysis were applied. It was determined that the power flux of wave energy in the Black Sea fluctuates: the highest value is 4.2 kW/m, the lowest is 1.4 kW/m. Results indicate significant correlations among the fluctuations of the average annual wave heights, periods, the power flux of wave energy, and teleconnection patterns of the North Atlantic Oscillation (NAO), the Atlantic Multi-decadal Oscillation (AMO), the Pacific Decadal Oscillation (PDO) and the East Atlantic/West Russia (EA/WR). It was revealed that, in positive phases of long-term periods of AMO (50–60 years) as well as PDO, NAO, and AO (40 years), a decrease of wave energy was observed; however, an increase in wave energy was observed in the positive phase of a 15-year period of NAO and AO. The positive phase of changes of EA/WR for periods 50–60, 20–25, and 13 years led to an increase of wave energy. The approximation functions of the oscillations of the average annual wave heights, periods, and the power flux of wave energy for the Black Sea are proposed.