We report the first observation of K*(892)0--> pi K in relativistic heavy ion collisions. The transverse momentum spectrum of (K*0+K*0)/2 from central Au+Au collisions at sqrt[sNN]=130 GeV is presented. The ratios of the K*0 yield derived from these data to the yields of negative hadrons, charged kaons, and phi mesons have been measured in central and minimum bias collisions and compared with model predictions and comparable e+e-, pp, and p-barp results. The data indicate no dramatic reduction of K*0 production in relativistic heavy ion collisions despite expected losses due to rescattering effects.