Earlier researchers studied and described the anomalous presence of Paleozoic fossils transplanted on the Quaternary upper Mid-Atlantic Coastal Plain (MACP) without scrupulous analysis of the fragmentary evidence on barrier islands and headlands bordering the Atlantic Ocean. The recent discovery of a trove of Paleozoic fossiliferous pebbles on the beaches of Long Beach Island, New Jersey (LBI) has reinvigorated interest in this shoreline region, an investigation of which is the focus of the present report. Surveys of three linearly extensive New Jersey beaches suggest that only replenished beaches, such as LBI, potentially harbor fossils. The natural, undisturbed beaches of Island Beach State Park and Brigantine Wildlife Refuge exhibit only complete modern mollusks on the foreshore and molluscan shards on the backshore without gravel and are devoid of fossils. Prospecting both types of Atlantic Ocean beaches suggests that replenished beaches initially carry Paleozoic fossils and gravel but eventually revert to a more natural state so that only recently replenished beaches may be expected to reveal significant fossils and gravel on the surface. Scrutiny of fossils found on replenished beaches of LBI reveals two distinct types of fossiliferous pebbles; Irregular shaped, rough surface with pristine fossils regarded as glaciogenic and a second smaller type of rounded, smooth surface with abraded fossils regarded as fluviogenic. It is notable that fossiliferous pebbles and gravel are well sorted and range from 5 – 20 millimeters in maximum dimension mixed with gravel of the same size. Maximum size is limited by screens in the dredge outflow equipment. Offshore stratigraphy suggests that the irregular pebbles are embedded in the Pleistocene-Recent veneer, and the rounded type from the underlying fluvial Miocene-Pliocene deposits. This unequal distribution suggests that dredging for beach replenishment on LBI taps the Pleistocene veneer deposits but occasionally penetrates to the underlying more gravelly fluvial Miocene-Pliocene. Examples of these two types are provided with the complete inventory of specimen posted in the Data Repository.