Primordial Black Holes (PBH's) can form in the early Universe from the collapse of large density fluctuations. Tight observational limits on their abundance constrain the amplitude of the primordial fluctuations on very small scales which can not otherwise be constrained, with PBH's only forming from the extremely rare large fluctuations. The number of PBH's formed is therefore sensitive to small changes in the shape of the tail of the fluctuation distribution, which itself depends on the amount of non-Gaussianity present. We study, for the first time, how quadratic and cubic local non-Gaussianity of arbitrary size (parameterised by f_nl and g_nl respectively) affects the PBH abundance and the resulting constraints on the amplitude of the fluctuations on very small scales. Intriguingly we find that even non-linearity parameters of order unity have a significant impact on the PBH abundance. The sign of the non-Gaussianity is particularly important, with the constraint on the allowed fluctuation amplitude tightening by an order of magnitude as f_nl changes from just -0.5 to 0.5. We find that if PBH's are observed in the future, then regardless of the amplitude of the fluctuations, non-negligible negative f_nl would be ruled out. Finally we show that g_nl can have an even larger effect on the number of PBH's formed than f_nl.