A method, system and computer program product are disclosed for rateless compression of non-binary sources. In one embodiment, the method comprises representing a sequence of non-binary source symbols as a sequence of sets of binary values; selecting a code for compressing the sets of binary values; determining a puncturing pattern, based on the selected code; and puncturing the sets of binary values, in patterns based on the puncturing pattern, to form a sequence of unpunctured values. A sequence of computed syndromes is determined based on the sequence of non-binary source symbols; and the sequence of unpunctured values and the sequence of computed syndromes are combined to form an output stream of data representing said sequence of non-binary source symbols. In one embodiment, none of the sets of binary values is punctured completely, and, for example, each of the sets of binary values may be punctured only partially.