We report the first observation of two Cabibbo-suppressed decay modes of the B0_s meson. Using a sample of p-pbar collisions at sqrt{s}=1.96 TeV corresponding to 5.9 fb-1 of integrated luminosity collected with the CDFII detector at the Fermilab Tevatron, we search for new B0_s decay modes in a sample of events containing J/psi to mu+ mu- decays. We reconstruct a B0_s to J/psi K*(892)0 signal with K^*(892)0 to K+ pi-, observing a yield of 151 +/- 25 events with a statistical significance of 8.0 sigma. We also reconstruct a B0_s to J/psi K0_S signal with K0_S to pi+ pi-, observing a yield of 64 +/- 14 events with a statistical significance of 7.2 sigma. From these yields, we extract the branching ratios B(B0_s -> J/psi K*(892)0)= (8.3 +/- 3.8) x 10{-5} and B(B0_s -> J/psi K0)= (3.5 +/- 0.8) x 10{-5}, where statistical, systematic and fragmentation fraction uncertainties are included in the combined uncertainty.