天正7年(1579年)、上杉氏憲の嫡男として誕生した。
父は後北条氏に従っており、小田原征伐で所領を失う。当初は父に従い信濃国で暮らすが、元和3年(1617年)に播磨国平福藩主、のち赤穂藩主となる池田輝興に仕える。
正保2年(1645年)3月15日、輝興は突如発狂し、正室の亀子姫をはじめ、侍女数人を斬殺する事件を起こしたため、3月20日に改易された(「正保赤穂事件」)。その身柄は甥で岡山藩主だった池田光政預かりとなり、それに従い憲俊も岡山へ随行した。
一説には慶長5年(1600年)の関ヶ原の戦いの直前に、上杉景勝から仕官の誘いがあったとも云われるが、定かではない。