1954年年底，斯塔申斯基被賦予一個全新的身份：約瑟夫·萊曼，一個生於波蘭的日耳曼族人。
1956年，斯塔申斯基開始被克格勃啟用。這時他已成為一個忠實的蘇聯間諜。雖然作為見習間諜，斯塔申斯基還有許多東西要學，但克格勃已經開始交給他任務了：暗殺流亡在德國的烏克蘭政治家裏貝特。第一次盯梢，斯塔申斯基感到非常不自在，好像全世界都在跟蹤自己，又好像裏貝特早已認出了他。為了掩飾內心的不安，斯塔申斯基戴上了墨鏡。漸漸地斯塔申斯基終於穩定下來，克服了恐懼心理，終於不留痕跡地完成了對裏貝特的暗殺行動。
1958年5月，斯塔申斯基被派往鹿特丹，奉命監視“烏克蘭民族主義者組織”慕尼黑分部的領導人、烏克蘭抵抗運動領導人中最傑出的人物班德拉。
正好在這時，斯塔申斯基熱戀上了英格·波爾小姐，一個普通的德國姑娘，一個改變了斯塔申斯基命運的女人。隨著時間的推移，無情的間諜活動正在迫使斯塔申斯基陷入一種無法忍受的處境，要麼繼續充當克格勃的殺手，要麼繼續喜歡英格·波爾，與她終身為伴，被克格勃拋棄。然而，莫斯科方麵早已獲悉斯塔申斯基偷偷摸摸的戀愛生活，而他未被幹掉的原因，主要是他在英格麵前一直保持著假身份。
1959年4月，他們秘密定婚。
不久，克格勃向他發出限期幹掉班德拉的命令。終於有一天，他看到班德拉獨自一人回到住所，沒有保鏢。斯塔申斯基搶先進了屋，走上樓梯等待班德拉進來。當聽到大門被打開時，他走下樓梯，清楚地看到班德拉的右臂上挎著一隻小菜籃，正在用力地抽著卡在鎖眼中的鑰匙。“不上班嗎？”斯塔申斯基問道，班德拉還沒有來得及反應，便覺得眼前一片酸霧，片刻，便失去了知覺。斯塔申斯基迅速拿出紗布包著的另一種解毒藥，急速地在大門上將它敲碎，吸入氣霧。
他環視四周，發現並無他人，便飛快地離開了這所房子。第二天，斯塔申斯基乘頭班飛機飛往柏林，向克格勃報告他已完成任務。
由於成功地完成了任務，斯塔申斯基被莫斯科授予紅旗勳章，這對斯塔申斯基來說簡直是異想天開之事，他從來沒有得過如此高的獎賞。可是想到要去莫斯科，要與他親愛的英格·波爾分別，甚至可能是從此分手，斯塔申斯基不由心情沉重起來。他痛切地知道，這種獎勵隻是一種虛幻騙人的東西而已，並不意味著可以過一種更美好、更自由的生活。斯塔申斯基感到緊張的另一個原因是，對這次殺人的細節，克格勃問得要比上次仔細得多。幾個蘇聯人對班德拉的死已作了檢查，並且告訴他，“這次謀殺並沒有做得像上次那樣完美無缺”。西德警察當局對班德拉突然死亡作了調查。在進行屍體解剖時，發現他臉上有被玻璃碎片劃破的地方，德國警方懷疑是由氰酸致毒而死。克格勃決定，在事情平靜下來前，斯塔申斯基應當留在莫斯科。12月，蘇共中央委員會的領導成員、克格勃的頭子謝列平親手授予他紅旗勳章，並要求他暫時呆在莫斯科，等待新的時機。在莫斯科的日子裏，斯塔申斯基非常想念他的女友英格·波爾。他為曾向英格說過一次謊而擔憂。當時他不願意承認他是去莫斯科，而謊稱是去波蘭出差。這時，他已經開始考慮要逃脫他所厭惡的殺人行當，並拿定主意，將來決不再幹殺人的勾當。盡管如此，他還是不敢向英格啟齒，吐露自己的真情。