A hollow fiber carbon membrane is provided, which has excellent gas separation performance, unbreakable flexibility and high utility. The hollow fiber carbon membrane comprises carbonized substance obtained by calcination of a hollow fiber-like material formed from a polyphenylene oxide derivative, and has an external diameter in the range of 0.08 mm to 0.25 mm. The polyphenylene oxide derivative substantially comprises repeating units represented by the following (a) and (b) (in the structural formula, R11 and R12 independently represent hydrogen atom or sulfone group, except that R11 and R12 are both hydrogen atoms), wherein the ratio A (%) of the repeating unit (b) to the repeating units (a)+(b) satisfies 15%