First results on charm quarkonia production in heavy ion collisions at the Relativistic Heavy Ion Collider (RHIC) are presented. The yield of J/Psi's measured in the PHENIX experiment via electron-positron decay pairs at mid-rapidity for Au-Au reactions at sqrt(s_NN) = 200 GeV are analyzed as a function of collision centrality. For this analysis we have studied 49.3 million minimum bias Au-Au reactions. We present the J/Psi invariant yield dN/dy for peripheral and mid-central reactions. For the most central collisions where we observe no signal above background, we quote 90% confidence level upper limits. We compare these results with our J/Psi measurement from proton-proton reactions at the same energy. We find that our measurements are not consistent with models that predict strong enhancement relative to binary collision scaling.