A transcatheter valve prosthesis (100, 1200) comprising: a tubular stent (102, 1202) having a compressed configuration for delivery within a vasculature and an expanded configuration for deployment within a native heart valve; a prosthetic valve component disposed within and secured to the stent; and an anti-paravalvular leakage component (330, 1230) coupled to and encircling an outer surface (103, 1203) of the tubular stent to seal gaps between the valve prosthesis and surrounding native tissue, characterized in that, according to a first alternative, the anti-paravalvular leakage component includes a radially-compressible annular scaffold (332, 832, 1032A) and a membrane of impermeable material extending over an outer surface of the annular scaffold, wherein the annular scaffold is a sinusoidal patterned ring of self-expanding material including a plurality of peaks, a plurality of valleys, and a plurality of segments with opposing peaks and valleys being formed between a pair of adjacent segments, the anti-paravalvular leakage component having an expanded configuration in which at least the plurality of segments curve radially away from the outer surface of the tubular stent; and in that, according to a second alternative, the anti-paravalvular leakage component includes a plurality of self-expanding segments and an annular sealing element coupled to inner surfaces of the segments, a first end and a second end of each segment being coupled to the outer surface of the tubular stent, wherein the anti-paravalvular leakage component has an expanded configuration in which the segments curve radially away from the outer surface of the tubular stent and the annular sealing element is positioned between the outer surface of the tubular stent and inner surfaces of the segments. a tubular stent (102, 1202) having a compressed configuration for delivery within a vasculature and an expanded configuration for deployment within a native heart valve; a prosthetic valve component disposed within and secured to the stent; and an anti-paravalvular leakage component (330, 1230) coupled to and encircling an outer surface (103, 1203) of the tubular stent to seal gaps between the valve prosthesis and surrounding native tissue, characterized in that, according to a first alternative, the anti-paravalvular leakage component includes a radially-compressible annular scaffold (332, 832, 1032A) and a membrane of impermeable material extending over an outer surface of the annular scaffold, wherein the annular scaffold is a sinusoidal patterned ring of self-expanding material including a plurality of peaks, a plurality of valleys, and a plurality of segments with opposing peaks and valleys being formed between a pair of adjacent segments, the anti-paravalvular leakage component having an expanded configuration in which at least the plurality of segments curve radially away from the outer surface of the tubular stent; and in that, according to a second alternative, the anti-paravalvular leakage component includes a plurality of self-expanding segments and an annular sealing element coupled to inner surfaces of the segments, a first end and a second end of each segment being coupled to the outer surface of the tubular stent, wherein the anti-paravalvular leakage component has an expanded configuration in which the segments curve radially away from the outer surface of the tubular stent and the annular sealing element is positioned between the outer surface of the tubular stent and inner surfaces of the segments.