Palmyra Atoll, in the Line Islands of the equatorial Pacific, supports one of the largest remaining native stands of Pisonia grandis forest in the tropical Pacific Ocean. In 2003, we surveyed terrestrial arthropods in order to document extant native and introduced species richness, compare these lists to historical records, and assess potential threats to native species and ecosystem integrity. In total, 115 arthropod taxa were collected, bringing the total number of taxa recorded since 1913 to 162. Few native species were collected; most taxa were accidental introductions also recorded from the Hawaiian Islands, the presumed main source of introductions to Palmyra. The overlap with previous historical surveys in 1913 and 1948 was low (<40%) and new species continue to establish, with one species of whitefly reaching pest status between 2003 and 2005. We observed numerous dead or dying large Pisonia grandis, and the green scale Pulvinaria urbicola (Coccidae) was particularly abundant on trees of poor health. Abundant introduced ants, particularly Pheidole megacephala, tended this and other hemipterans feeding on both native and introduced plants. We hypothesize that the Pheidole--Pulvinaria facultative mutualism is causing the decline of Pisonia grandis. Because of the unique properties of Pisonia grandis forest on oceanic atolls, its importance for nesting seabirds, and its alarming global decline, immediate conservation efforts should be directed at controlling introduced Hemiptera and disrupting their mutualisms with non-native ants on Palmyra Atoll.