Underwater wireless power transfer (WPT) has become one reliable and safe method of charging autonomous underwater vehicles (AUVs). The transmission efficiency of the traditional single-coil structure will significantly decrease as the load value or transmission distance fluctuates. To achieve relatively high transmission efficiency over a wide range of transmission distances, a novel electromagnetic Halbach array (EHA) structure is constructed and analyzed. Both EHA and single-coil structures are modeled using the electromagnetic finite element analysis software ANSYS, upon which experiments are conducted using prototypes. The power transfer performances in the three environments (air, tap-water and seawater), different transmission distances and working frequencies are compared. The experimental results indicate that 150 kHz is the optimal working efficiency for both structures. Also, it is found that in underwater environments, the transmission efficiency is lower compared with that in the air, with around 5% decline in the EHA structure and more than 10% decline in the single-coil structure. Hence, EHA structure has better transmission performance than single-coil structure regardless of the power transmission medium.