We search for new charmless decays of neutral b hadrons to pairs of charged hadrons, using 1 fb[superscript -1] of data collected by the CDF II detector at the Fermilab Tevatron. We report the first observation of the B[subscript s][superscript 0]→K[superscript -]π[superscript +] decay and measure B[subscript s][superscript 0]→K[superscript -]π[superscript +]=(5.0±0.7(stat)±0.8(syst))×10[superscript -6]. We also report the first observation of charmless b-baryon decays, and measure B(Λ[subscript b][superscript 0]→pπ[superscript -])=(3.5±0.6(stat)±0.9(syst))×10[superscript -6] and B(Λb0→pK-)=(5.6±0.8(stat)±1.5(syst))×10[superscript -6]. No evidence is found for other modes, and we set the limit B(B[subscript s][superscript 0]→π[superscript +]π[superscript -])<1.2×10[superscript -6] at 90% C.L. Academy of Finland Slovak R&D Agency Programa Consolider-Ingenio 2010, Spain Ministerio de Ciencia e Innovación, Spain Russian Foundation for Basic Research Institut National de Physique Nucleaire et Physique des Particules/CNRS Royal Society, United Kingdom Science and Technology Facilities Council, United Kingdom Korean Research Foundation Korean Science and Engineering Foundation Bundesministerium für Bildung und Forschung, Germany Alfred P. Sloan Foundation Swiss National Science Foundation National Science Council of the Republic of China Natural Sciences and Engineering Research Council of Canada Ministry of Education, Culture, Sports, Science and Technology of Japan Italian Istituto Nazionale di Fisica Nucleare National Science Foundation United States Department of Energy