Astrophysical magnetic reconnection sites have long been expected to be sources of high-energy particles. Recent observations of high-energy gamma-ray flares from the Crab nebula and models of gamma-ray bursts and TeV blazars have motivated us to better understand magnetic reconnection and its associated particle acceleration in plasma conditions where the magnetic energy is dominant. We will present fully kinetic particle-in-cell simulations of anti-parallel magnetic reconnection in the highly magnetized regime (the magnetization parameter sigma >> 1). The magnetic energy is converted efficiently into kinetic energy of nonthermal relativistic particles in a power-law spectrum. For a sufficiently large system and strong magnetic field, the power-law index approaches "p=1". The dominant acceleration mechanism is a first-order Fermi process accomplished through the curvature drift motion of particles in magnetic flux tubes along the electric field induced by fast plasma flows. We will also present an analytical model for the formation of power-law distribution and show the nonthermal distribution may be a common feature of magnetically dominated reconnection.