楊義臣，代人，本姓尉遲。
父親尉遲崇，仕北周，為儀同大將軍，率兵鎮守恆山。
當時，隋高祖任定州總管。
尉遲崇知道高祖相貌非常，常常與他交結，高祖對他很親近。
高祖為北周丞相後，尉遲迥造反，尉遲崇因與反賊是同族的緣故，把自己關在牢裡，派人赴京請罪。
高祖下書慰問他，讓他乘驛車回朝，把他老是安排在身邊。
開皇初年，封尉遲崇為秦興縣公爵。
過了一年多，他隨行軍總管達奚長儒到周盤反擊突厥，力戰而死。
追贈他為大將軍、豫州刺史，以尉遲義臣承襲他的官爵。
當時義臣還年幼，養育在宮中。
不滿二十歲，就已奉詔像千牛那樣當侍衛幾年了，皇上給他的賞賜很多。
皇上閒談時曾說到過去的一些朋友，看著義臣，嗟歎很久。
因此下詔書說：「我剛受命登基時，群凶尚未平定，有識之士，有足可懷。
尉遲義臣與尉遲迥，本同骨肉。
尉遲迥既已作亂於鄴城，其父尉遲崇當時在常山，統帥部隊，既與尉遲迥相鄰，又與尉遲迥是至親。
他知道逆順的大理，認識天人的意思，就陳述丹心，擔心被反賊牽連，於是自己把自己抓起來，請求到丞相府來。
到北狄入侵時，他又橫戈殺敵，輕生重義，馬革裹屍。
他的節操表現在生死之上，他的事跡貫穿於人間地下。
即使是給他高官大賞，並讓官爵延及於他的子孫，也不足以表彰他松柏一樣的壯志，也不足以表彰他的節義門庭。
義臣，可賜姓楊氏，賜錢三萬貫，酒三十斛，米麥各百斛，把他編入楊門家譜，作皇帝我的堂孫。」不久，授楊義臣為陝州刺史。
義臣謹慎忠厚，長於騎馬射箭，有將領之才，因此皇上很器重他。
其後，突厥達頭可汗進犯邊塞，義臣以行軍總管身份，率領步兵、騎兵三萬人馬，出白道，與賊人相遇，交戰，大破賊人。
次年，突厥人又進犯邊塞，雁門、馬邑二地多受其害。
義臣打擊他們，他們於是逃到塞外，義臣率兵追擊，追到大斤山，與賊人相遇。
當時，太平公史萬歲的人馬也趕到了，義臣與萬歲合力擊賊，大敗突厥兵。
史萬歲被楊素陷害致死，義臣的功勞竟不被著錄。
仁壽初年，義臣拜授朔州總管，賜給他御用的甲冑。
煬帝繼位後，漢王楊諒作亂於并州。
當時，代州總管李景被漢王的部將喬鍾葵包圍，有詔讓義臣去救援他。
義臣率領騎兵、步兵二萬，夜出西陘，快天亮時，已趕了幾十里路。
喬鍾葵偵悉義臣人馬少，於是全部上陣來抵抗義臣。
鍾葵的副將王拔，驍勇無敵，特善用矛肖，射他又射不中，他常帶幾個騎兵衝鋒陷陣。
義臣特擔心他，於是招募能夠抵擋王拔的人。
車騎將軍楊思恩請求與王拔交戰。
義臣見思恩氣貌雄勇，對他說：「真是壯士！」賜給他一卮酒。
思恩遠遠望見王拔站在陣後，就把酒斛往地上一丟，策馬而赴敵。
思恩沖了兩次，都沒有克敵制勝，義臣就又選十幾個騎兵隨他前去。
思恩於是向前猛衝，殺了幾個敵人，一直衝到王拔的軍旗下。
兩人短兵交戰，思恩的隨從騎兵退後，於是思恩被王拔所殺。
王拔於是乘勝進軍，義臣軍退了十幾里。
義臣於是贖回思恩的屍體，放聲痛哭，三軍無不流淚。
思恩的隨從騎兵都被腰斬。
義臣因自己兵少，於是把軍中的牛和驢子全部清出來，清了幾千頭，又令兵卒幾百人，每人拿一個鼓，偷偷地把牛和驢子趕到山谷裡，出其不意。
吃了晚飯，義臣又與鍾葵交戰，兩軍剛交手，義臣就命令驅趕牛和驢子的疾速前進。
一時間，戰鼓震天，塵埃彌天，鍾葵軍不知究竟，還以為是伏兵大發，因此大大地潰敗。
義臣縱兵反擊，大破鍾葵。
義臣因戰功升任上大將軍，賜縑采二千段，雜采五百段，女妓十人，良馬二十匹。
繼而授他為相州刺史。
三年後，調義臣任宗正卿。
不久，轉任太僕卿。
隨煬帝征討吐谷渾。
煬帝令義臣駐軍於琵琶峽，軍營相連達八十里，南接元壽，北連段文振，把吐谷渾國主包圍在覆袁州。
此後又隨煬帝征討遼東，義臣率軍直指肅慎道。
到了鴨綠江，與乙支文德交戰，義臣每次都當先鋒，一天打了七次勝仗。
後與各路人馬都打了敗仗，竟坐罪免職。
不久復職。
次年，以義臣為副將，與大將軍宇文述去進攻平壤。
到了鴨綠江，碰上楊玄感作亂，班師回朝，代理趙郡太守。
妖賊向海公聚眾作亂，寇掠於扶風、安定兩地之間，義臣奉聖旨掃平了他們。
繼而隨煬帝再征討遼東，義臣升為左光祿大夫。
當時渤海人高士達、清河人張金稱，都相聚為盜，已有幾萬之眾，攻陷郡縣。
煬帝派將軍段達進討，不能取勝。
有詔讓義臣率領從遼東回來的兵馬幾萬去進剿。
義臣大破高士達，斬了張金稱。
又收拾降兵，進入豆子赹，討伐格謙，活捉了他。
義臣報告了朝廷。
煬帝厭惡他的威名，急急追他入朝。
賊人因此又強大起來。
義臣因軍功升任光祿大夫，不久拜授禮部尚書。
不久，在官任上去世。