We search for new charmless decays of neutral b hadrons to pairs of charged hadrons, using 1  fb−1 of data collected by the CDF II detector at the Fermilab Tevatron. We report the first observation of the B0s→K−π+ decay and measure B(B0s→K−π+)=(5.0±0.7(stat)±0.8(syst))×10−6. We also report the first observation of charmless b-baryon decays, and measure B(Λ0b→pπ−)=(3.5±0.6(stat)±0.9(syst))×10−6 and B(Λ0b→pK−)=(5.6±0.8(stat)±1.5(syst))×10−6. No evidence is found for other modes, and we set the limit B(B0s→π+π−)<1.2×10−6 at 90% C.L.