An ultra-sensitive method for arsenic (As) speciation analysis based on selective hydride generation (HG) with preconcentration by cryotrapping (CT) and inductively coupled plasma-mass spectrometry (ICP-MS) detection is presented. Determination of the valency of the As species is performed by selective HG without prereduction (trivalent species only) or with L-cysteine prereduction (sum of tri- and pentavalent species). Methylated species are resolved on the basis of thermal desorption of the formed methyl substituted arsines after collection at −196 °C. Limits of detection of 3.4, 0.06, 0.14 and 0.10 pg mL⁻¹ (ppt) were achieved for inorganic As, mono-, di- and trimethylated species, respectively, from a 500 μL sample. Speciation analysis of river water (NRC SLRS-4 and SLRS-5) and sea water (NRC CASS-4, CASS-5 and NASS-5) reference materials certified to contain 0.4 to 1.3 ng mL⁻¹ total As was performed. The concentrations of methylated As species in tens of pg mL⁻¹ range obtained by HG-CT-ICP-MS systems in three laboratories were in excellent agreement and compared well with results of HG-CT-atomic absorption spectrometry and anion exchange liquid chromatography-ICP-MS; sums of detected species agreed well with the certified total As content. The HG-CT-ICP-MS method was successfully used for analysis of microsamples of exfoliated bladder epithelial cells isolated from human urine. Here, samples of lysates of 25 to 550 thousand cells contained typically tens of pg up to ng of iAs species and from single to hundreds of pg of methylated species, well within detection power of the presented method. A significant portion of As in the cells was found in the form of the highly toxic trivalent species.