We report the first observation of two Cabibbo-suppressed decay modes of the B0s meson. Using a sample of pp collisions at s√=1.96  TeV corresponding to 5.9  fb−1 of integrated luminosity collected with the CDF II, the collider detector at the Fermilab Tevatron, we search for new B0s decay modes in a sample of events containing J/ψ→μ+μ− decays. We reconstruct a B0s→J/ψK∗(892)0 signal with K∗(892)0→K+π−, observing a yield of 151±25 events with a statistical significance of 8.0σ. We also reconstruct a B0s→J/ψK0S signal with K0S→π+π−, observing a yield of 64±14 events with a statistical significance of 7.2σ. From these yields, we extract the branching ratios B(B0s→J/ψK∗(892)0)=(8.3±3.8)×10−5 and B(B0s→J/ψK0)=(3.5±0.8)×10−5, where statistical, systematic, and fragmentation-fraction uncertainties are included in the combined uncertainty.