Gas phase complexes between niobium atoms and the polycyclic aromatic hydrocarbons (PAHs) pyrene (C16H10) and coronene (C24H12) are produced in a molecular beam using laser vaporization in a pulsed nozzle cluster source. Cation complexes are studied with time-of-flight mass spectrometry and mass-selected photodissociation. Mass distributions and fragmentation patterns for Nb-x-(PAH)(y). complexes are significantly different from those found previously for other M-x-(PAH)(y) complexes. Masses indicating the formation of metal-hydrocarbons and metal-carbides are prominent. Larger complexes add intact PAH moieties to the strongly bound mono-metal adducts. Niobium is significantly more reactive with PAH species than other transition metals studied to date.