Internal quality of fresh and cold stored celery petioles of four different accessions (two green cultivars, one yellow cultivar and one yellow local ecotype) was characterised by descriptive analysis of sensory properties of aspect, flavour and texture, chemical determinations (organic acids, sugars, dietary fibre, flavonoids, carotenoids) and instrumental measurements of texture (stiffness, fracture toughness, maximum shear force). In the growing conditions as adopted in the experiment, different genotypes produced petioles with quite similar and low levels of dry matter, but with significant differences in some texture (flexibility, fracturability, hardness, crunchiness and fibrousness), flavour (odour and total flavour) and taste (saltiness and bitterness) attributes. After fortnight of cold storage (2 °C, 75–85% RH) differences between genotypes were still perceived in some texture attributes, particularly flexibility, fracturability and hardness. On the other hand, significant differences were no longer observed in total flavour, whereas lowered differences were still perceived in odour. Green type cultivars distinguished for higher fibrousness, bitter taste and harsh after effect. Sweetness was not linearly correlated to total and individual sugar contents, whereas organic acids content was probably too low to cause perceivable sourness; moreover, the sensory perception of fibrousness during chewing seemed to be related to other constituents in addition to fibre. Finally the low contents of flavones (apigenin 0.76–3.11 mg/kg and luteolin 0.50–1.74 mg/kg) and carotenoids (lutein 0.60–1.58 mg/kg and β-carotene 0.20–0.71 mg/kg) in all genotypes suggested a poor relevance of celery petioles devoid of leaves as dietary sources of these bioactive compounds.