Sinh ngày 4/11/1931 ở làng Barszczowice, tỉnh Lviv. Stashynsky phát hiện ra tài năng có một không hai của mình theo cách tình cờ ngay sau khi Thế chiến II kết thúc. Bị bắt giữ vì đi tàu không có vé, cậu sinh viên túng tiền của Học viện Sư phạm Lviv đã được tình báo Liên Xô tuyển mộ ngay tại chỗ. Chàng trai trẻ được bộ máy an ninh Liên Xô quan tâm vì xuất thân trong một gia đình có quan hệ mật thiết với phong trào dân tộc chủ nghĩa Ukraine, đứng đầu là Stepan Bandera, nhân vật chống cộng quyết liệt và đã cam kết trung thành với Adolf.
Trong một vài năm, Stashynsky đã trau dồi kỹ năng thông qua việc thâm nhập vào các kết nối ngầm của những người theo chủ nghĩa dân tộc Ukraine và ám sát các nhân vật này cùng với các đồng nghiệp KGB. Thông thạo ngôn ngữ, quyết đoán và quan trọng nhất là sự ranh mãnh là những điều tạo nên một sát thủ bẩm sinh, phục vụ cho các kế hoạch quan trọng của Liên Xô.
Năm 1957, Stashynsky định cư tại Berlin dưới danh tính mới là Josef Lehmann. Ngày 12/10/1957, Lev Rebet – một trong những nhân vật chủ chốt của phong trào dân tộc chủ nghĩa Ukraine lưu vong – đến nơi làm việc ở Munich. Khi Rebet đang đi lên cầu thang đến tòa nhà văn phòng, anh nhìn thấy một người đàn ông trẻ tuổi. Khi đến gần, người đàn ông này giơ tay, bắn một phát vào mặt Rebet và nhanh chóng rời khỏi tòa nhà. Rebet chết ngay lập tức. Sát thủ chuyên nghiệp đứng sau vụ giết người là Bohdan Stashynsky.
Stashynsky được giao nhiệm vụ tiếp theo là thủ tiêu người đàn ông bị Moscow ghét bỏ – Stepan Bandera, người sống ở Munich, cũng dưới một danh tính khác. Sau khi thử nghiệm thành công khẩu súng phun sương độc để ám sát nạn nhân đầu tiên – Lev Rebet – mà không để lại dấu vết, vào ngày 15/10/1959, Stashynsky bám theo đến tận nhà mục tiêu. Đến gần Bandera, người đang loay hoay với ổ khóa, tên sát thủ hỏi xem chìa khóa có ổn không. Khi Bandera ngẩng đầu lên để trả lời, Stashynsky bắn ra một làn sương độc. Người đàn ông gục xuống ngay lập tức và chết ngay sau đó.
Nhiệm vụ hoàn thành. Lẽ ra Stashynsky sẽ vui vẻ tận hưởng phần thưởng ở Moscow, nhưng thành tựu này hoàn toàn bị lu mờ bởi một thứ khác. Khi ở Berlin, điệp viên Liên Xô đã phải lòng Inga Pohl – một phụ nữ người Đức, trớ trêu thay, lại là một nhân vật chống cộng quyết liệt. Stashynsky không biết rằng tình yêu với một phụ nữ Đức sau này đã khiến sự nghiệp anh lụi bại. Bất chấp sự phản đối trong KGB, Stashynsky vẫn nhất quyết kết hôn với người phụ nữ mình yêu. Người phụ nữ Đức không hề biết về nghề nghiệp của chồng minh. Khi Stashynsky mở lòng với cô, Pohl đã rất sốc, nhưng đã không tố cáo người tình.
Bất ngờ hơn, KGB sau đó đã cho phép Stashynsky kết hôn với người phụ nữ mà anh lựa chọn và cả hai định cư ở Moscow. Khi Pohl sinh con trai cho Stashynsky, cô được phép về thăm Đức. Tận hưởng cuộc sống gia đình hạnh phúc, Stashynsky bắt đầu phân vân giữa việc nuôi dưỡng gia đình và phục vụ trong KGB. Cuối cùng, anh quyết định chọn từ bỏ tất cả để đến phương Tây. Chỉ 4 tháng sau khi chào đời, con trai của Stashynsky qua đời tại Đức. Người điệp viên được phép tham dự lễ tang, nhưng anh đã tận dụng cơ hội để trốn khỏi Liên Xô và tiết lộ chi tiết về hoạt động của mình cho CIA.
Vào ngày 13/8/1961, Stashynsky và vợ lẻn ra khỏi nhà, bỏ lại chiếc quan tài chưa chôn cùng đứa con đã qua đời của họ. Stashynsky đầu hàng cảnh sát ở Tây Đức và sau đó được giao cho các nhân viên CIA. Tiết lộ của Stashynsky đã mang đến một phiên tòa gây tiếng vang lớn, nơi các vụ giết người ở Đức được làm sáng tỏ. Bị cáo buộc là hung thủ của những vụ giết người có động cơ chính trị, Stashynsky nhận bản án tương đối ngắn, chỉ 8 năm tù. Inga Pohl ly hôn khi chồng bị kết án vào năm 1964, trước khi Stashynsky được tạm tha vào năm 1967.
Sau khi được trả tự do, Stashynsky đã che đậy tung tích của mình chuyên nghiệp như cái cách gã xóa bỏ dấu vết khi giết người. Theo nhiều nguồn tin khác nhau, Stashynsky có thể đã đến Mỹ hoặc Nam Phi, thay đổi diện mạo bằng cách phẫu thuật thẩm mỹ. Không ai biết liệu sát thủ này đã nghỉ hưu hay còn sống đến ngày nay hay không.
